Submodulär optimering spelar en nyckelroll i många verkliga problem. I många verkliga scenarier är det också nödvändigt att hantera osäkerhet, och potentiellt störande händelser som bryter mot begränsningar i stokastiska inställningar måste undvikas. I detta dokument undersöker vi submodulära optimeringsproblem med slumpmässiga begränsningar. Vi ger en första analys av approximationen beteende av populära giriga algoritmer för submodulära problem med slumpen begränsningar. Våra resultat visar att dessa algoritmer är mycket effektiva när du använder surrogatfunktioner som uppskattar begränsningar överträdelser baserat på Chernoff gränser. Dessutom undersöker vi algoritmernas beteende på populära sociala nätverksproblem och visar att högkvalitativa lösningar fortfarande kan erhållas även om det finns starka restriktioner på grund av slumpen. Submodulär optimering har studerats för ett brett spektrum av olika begränsningstyper, se t.ex. (KG14) och referenser som nämns där. Många av resultaten på monotona submodulära funktioner är baserade på enkla giriga urvalsstrategier som kan uppnå de bästa
Doerr m.fl. REF har undersökt anpassningar av klassiska giriga algoritmer för optimering av submodulära funktioner med slumpmässiga begränsningar av knapsack typ.
Optimization of Chance-Constrained Submodular Functions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}