I Stochastic Orientering problem, vi ges en metrisk, där varje nod har också ett jobb som ligger där med någon deterministisk belöning och en slumpmässig storlek. (Tänk på jobben som sysslor man måste springa, och storleken som den tid det tar att göra uppgiften.) Målet är att anpassa sig till vilka noder som ska besökas för att maximera den totala förväntade belöningen, med förbehåll för begränsningen att den totala ressträckan plus den totala storleken av jobb som behandlas är som mest en given budget för B. (d.v.s. vi får belöning för alla de sysslor vi avslutar i slutet av dagen). Ett jobbs (slumpmässiga) storlek är inte känd förrän det är helt bearbetat. Därför kombinerar problemet aspekter av både den stokastiska knapsack problem med osäkra artikelstorlekar och deterministiska orientering problem med att använda en begränsad restid för att maximera samlade belöningar som finns vid noder. I detta dokument presenterar vi en approximationsalgoritm med konstant faktor för den bästa icke-adaptiva politiken för det stokastiska orienteringsproblemet. Vi visar också en liten adaptivitet gap-d.v.s. förekomsten av en icke-adaptiv politik vars belöning är minst en 1 log B-fraktion av den optimala förväntade belöning-och därför får vi också en O (log log B)-tillnärmning algoritm för adaptiv problem. Slutligen tar vi itu med fallet när noden belöningar är också slumpmässiga och kan korreleras med väntetiden, och ge en icke-adaptiv politik som är en O (log n log B)-uppskattning till den bästa adaptiva policyn för n-node metrics med budget B. Detta anslag är avsett att täcka åtaganden som återstår att reglera i enlighet med artikel 21 i förordning (EU) nr 1303/2013. Det finns en konstant-faktor approximationsalgoritm till optimal icke-adaptiv politik för stokastisk orientering. Observera att om vi kunde visa ett existentiellt bevis på en konstant anpassningsklyfta (som vi förmodar vara sann), ovan approximation för icke-adaptiva problem som vi visar omedelbart innebär en O(1)- approximation algoritm för adaptiv problem också. Vår andra uppsättning resultat är för en variant av problemet, en där både belöningar och jobbstorlekar är slumpmässiga och korrelerade med varandra. För detta korrelerade problem visar vi följande resultat: Theorem 1.4. Det finns en polynom-tidsalgoritm som ger en icke-adaptiv lösning för korrelerad stokastisk orientering, som är en O (log n log B)-uppskattning till den bästa adaptiva lösningen. Dessutom är det korrelerade problemet minst lika svårt som problemet med orientering med deadlines. Kom ihåg att vi bara vet en O(log n) approximation för orientering-med-deadlines problem [BBCM04]. Våra tekniker: De flesta av de tidigare anpassningsluckorna har visat sig genom att överväga en viss linjär programmeringsavkoppling som fångar upp de optimala adaptiva strategierna, och sedan visa hur man rundar en fraktionerad LP-lösning för att få en icke-adaptiv strategi. Men eftersom vi inte känner till någon god avkoppling för ens det deterministiska orienteringsproblemet, verkar detta tillvägagångssätt vara svårt att ta direkt. Så för att visa våra anpassningsgap resultat tvingas vi argumentera direkt om den optimala adaptiva strategin: vi använder martingale argument för att visa existensen av en väg (alias. icke-adaptiv strategi) i detta träd som ger en stor belöning. Vi kan sedan använda algoritmer för icke-adaptiva inställningar, som är baserade på reduktioner till orientering (med en ytterligare knapsack begränsning). Färdplan: Resten av dokumentet följer översikten ovan. Vi börjar med några definitioner i Avsnitt 2, och sedan definiera och ge en algoritm för knapsack orienteringsproblem som kommer att vara en avgörande sub-rutin i alla våra algoritmer i Avsnitt 3. Därefter motiverar vi vår icke-adaptiva algoritm genom att diskutera några halm-man lösningar och de fällor de faller i, i Avsnitt 4. Vi förklarar sedan och bevisar vår konstant-faktor icke-adaptiv algoritm i Sektion 5, vilket naturligt leder oss till vårt huvudresultat i Sektion 9, bevis på O (log log B)-adaptivity gap för StocOrient. Slutligen presenterar vi i sektion 13 den polylogaritmiska approximationen för problemet där belöningarna och storlekarna är korrelerade med varandra. För alla dessa resultat utgår vi från att vi inte får avbryta arbetstillfällen när vi väl har börjat arbeta med dem: i avsnitt 18 visar vi hur vi ska bevilja ansvarsfrihet för detta antagande. 2 Egentligen bör man verkligen ersätta det stokastiska jobbet med en deterministisk en av storlek E[min(S j, B − d(ρ, j))]] och belöna r j · Pr[S j + d(ρ, j) ≤ B], det är mycket lätt att lura algoritmen annars.
Det stokastiska orienteringsproblemet REF är en gemensam generalisering av både deterministisk orientering och stokastisk knapsack.
Approximation algorithms for stochastic orienteering
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Computer Science']}