I det submodulära omslaget problem, vi ges en icke-negativ monoton submodulär funktion f över en markuppsättning E objekt, och målet är att välja en minsta delmängd S. E sådan att f (S) = Q där Q = f (E). I den stokastiska versionen av problemet, vi ges m stokastiska objekt som är olika slumpmässiga variabler som självständigt inser för något objekt i E, och målet är att hitta en minsta uppsättning stokastiska objekt vars förverkligande R uppfyller f (R) = Q. Problemet fångar som ett specialfall stochastic set täcka problem och mer allmänt, stochastic täcker heltal program. En fullt adaptiv algoritm för stokastiskt submodulärt omslag väljer ett objekt att förverkliga och baserat på dess förverkligande, bestämmer vilket objekt att förverkliga nästa. En icke-adaptiv algoritm å andra sidan måste välja en permutation av objekt i förväg och förverkliga dem en efter en i den ordning som anges av denna permutation tills funktionsvärdet når Q. Kostnaden för algoritmen i båda fallen är antalet (eller kostnaderna) av poster som realiseras av algoritmen. Det är inte svårt att visa att även för täckningsfunktionen finns det fall där den förväntade kostnaden för en fullt adaptiv algoritm och en icke-adaptiv algoritm separeras av en (Q). Denna starka separation, som ofta kallas anpassningsgapet, är i skarp kontrast till de separationer som observerats inom ramen för stokastiska förpackningsproblem där prestandagapet för många naturliga problem är nära poly-tid approximabiliteten av den icke-stokastiska versionen av problemet. Motiverad av denna slående klyfta mellan kraften i adaptiva och icke adaptiva algoritmer, anser vi följande fråga i detta arbete: Behöver man full förmåga till anpassning för att få en nästan optimal lösning på stokastiska submodulära omslag? I synnerhet, hur garanterar prestandan förändras när en algoritm interpolerar mellan dessa två ytterligheter med hjälp av några rundor av anpassningsförmåga. I detta syfte definierar vi en r-round adaptiv algoritm för att vara en algoritm som väljer en permutation av alla tillgängliga objekt i varje runda k [r], och en tröskel τ k, och inser objekt i den ordning som anges av permutation tills funktionsvärdet är minst τ k. Permutationen för varje runda k väljs adaptivt baserat på förverkligandet i de föregående runderna, men beställningen inuti varje runda förblir fast oavsett de insikter som ses inuti omgången. Vårt huvudsakliga resultat är att för alla heltal r, det finns en poly-time r-round adaptiv algoritm för stokastisk submodulär cover vars förväntade kostnad är Õ(Q 1/r ) gånger den förväntade kostnaden för en fullt adaptiv algoritm. Före vårt arbete var ett sådant resultat inte känt även för r = 1 och när f är täckningsfunktionen. Å andra sidan visar vi att för alla r, det finns fall av stokastiska submodulära cover problem där ingen r-round adaptiv algoritm kan uppnå bättre än  under Q 1/r ) approximation till den förväntade kostnaden för en fullt adaptiv algoritm. Vårt lägre bundet resultat håller även för täckningsfunktion och algoritmer med obegränsad beräkningskraft. Därför visar vårt arbete att logaritmiska omgångar av anpassningsförmåga är nödvändiga och tillräckliga för att få nästan optimala lösningar på det stokastiska submodulära omslagets problem, och även få omgångar av anpassningsförmåga är tillräckliga för att kraftigt minska anpassningsklyftan.
Tillbaka till den adaptiva stokastiska minimikostnadstäckningen, när distribution p är fullt faktoriserad (dvs. resultaten är oberoende) och för specialfallet av stokastisk uppsättning täckning, REF visade nyligen att det finns en policy som med O(log(Q) / log(Q)) log(Q)) rundor av anpassningsförmåga uppnår en poly-logaritmisk approximation till den optimala sekventiella politiken.
Stochastic Submodular Cover with Limited Adaptivity
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}