Vi anser att problemet med stokastisk monoton submodulär funktion maximering, med förbehåll för begränsningar. Vi ger resultat om anpassningsluckor och om klyftan mellan de optimala offline- och onlinelösningarna. Vi presenterar ett förfarande som omvandlar ett beslutsträd (adaptiv algoritm) till en icke-adaptiv kedja. Vi bevisar att denna kedja uppnår minst τ gånger nyttan av beslutsträdet, över en produktdistribution och binärt tillstånd utrymme, där τ = min i,j Pr[x i = j]. Detta visar en anpassningsklyfta på 1 τ (som är 2 i fallet med en enhetlig fördelning) för problemet med stokastisk monoton submodulär maximering med tillståndsoberoende begränsningar. För en kardinalitetsbegränsning bevisar vi att en enkel adaptiv girig algoritm uppnår en approximationsfaktor på (1 − 1 e τ ) med avseende på den optimala offlinelösningen; tidigare har det bevisats att algoritmen uppnår en approximationsfaktor på (1 − 1 e ) med avseende på den optimala adaptiva onlinelösningen. Slutligen visar vi att det finns en icke-adaptiv lösning för det stokastiska maxtäckningsproblemet som ligger inom en faktor (1 - 1 e ) för den optimala adaptiva lösningen och inom en faktor för τ (1 - 1 e ) för den optimala offlinelösningen.
I REF studerades också problemet med stokastisk submodulär maximering under olika typer av begränsningar, inklusive knapsackbegränsningar.
Discrete Stochastic Submodular Maximization: Adaptive vs. Non-Adaptive vs. Offline
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}