I Stochastic Orientering problem, vi ges en finit metrisk utrymme, där varje nod innehåller ett jobb med någon deterministisk belöning och en slumpmässig bearbetningstid. Processtidsfördelningen är känd och oberoende mellan olika noder. Den faktiska handläggningstiden för ett arbete är dock inte känd förrän det är helt bearbetat. Målet är att beräkna en icke-förväntande politik för att besöka noder (och köra motsvarande jobb) för att maximera den totala förväntade belöningen, under förutsättning att den totala ressträckan plus den totala bearbetningstiden är som mest en given budget B. Detta problem kombinerar aspekter av den stokastiska knapsack problem med osäkra artikelstorlekar [18], samt deterministiska orienteringsproblem [8]. I detta dokument överväger vi både icke-adaptiv och adaptiv politik för stokastisk orientering. Vi presenterar en konstantfaktor approximationsalgoritm för den icke-adaptiva versionen, och en O (log log B) - approximation algoritm för den adaptiva versionen. Vi utvidgar båda dessa resultat till riktade mätvärden och ett mer allmänt sekvensorienterande problem. Slutligen, vi tar itu med problemet Stochastic Orientering när noden belöningar är också slumpmässiga och möjligen korrelerade med bearbetningstiden, och få en O (log n log B)-tillnärmning algoritm; här n är antalet noder i metriska. Alla våra resultat för en anpassningspolitik band också de motsvarande "anpassningsluckorna".
Gupta m.fl. REF utformade en O(1)-algoritm för bästa icke-adaptiva policy för stokastiska orienteringsproblem.
Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
{'venue': 'Math. Oper. Res.', 'journal': 'Math. Oper. Res.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}