Antag att vi får en submodulär funktion f över en uppsättning element, och vi vill maximera dess värde under vissa begränsningar. Goda approximationsalgoritmer är kända för sådana problem under både monotona och icke-monotona submodulära funktioner. Vi betraktar dessa problem i en stokastisk miljö, där element inte alla är aktiva och vi bara kan få värde från aktiva element. Varje element e är aktiv oberoende med några kända sannolikhet p e, men vi vet inte elementets status a priori. Vi får reda på det först när vi sonderar elementet e-probing avslöjar om det är aktivt eller inte, varefter vi kan använda denna information för att bestämma vilka andra element att sondera. Så småningom, om vi har en sond uppsättning S och en delmängd aktiva (S) av aktiva element i S, kan vi välja alla T  på aktiva (S) och få värde f (T ). Dessutom, sekvensen av element vi sondera måste uppfylla en given prefix-stängd begränsning-t.ex., dessa kan ges av en matris, eller en orientering begränsning, eller deadline, eller företräde begränsning, eller en godtycklig nedåtstängd begränsning-om vi kan sondera någon sekvens av element vi kan sondera alla prefix av det. Vad är en bra strategi för att undersöka element för att maximera det förväntade värdet? I detta dokument studerar vi gapet mellan adaptiva och icke adaptiva strategier för f är en submodulär eller en fraktionerat subadditiv (XOS) funktion. Om denna klyfta är liten kan vi istället fokusera på att hitta bra icke-anpassningsstrategier, som är lättare att hitta och representera. Vi visar att anpassningsgapet är en konstant för monotona och icke-monotona submodulära funktioner, och logaritmiska för XOS-funktioner av liten bredd. Dessa gränser är nästan snäva. Våra tekniker visar nya sätt att argumentera om det optimala adaptiva beslutsträdet för stokastiska problem.
I REF studerades anpassningsgapet för stokastisk submodulär maximering med en mängd prefix-slutna begränsningar under den miljö där fördelningen av varje objekt är Bernoulli.
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}