Vi studerar de stokastiska versionerna av en bred klass av kombinatoriska problem där vikterna av elementen i inmatningsdatasetet är osäkra. Den klass av problem som vi studerar inkluderar kortaste vägar, minsta vikt spänner träd, och minimal vikt matchningar, och andra kombinatoriska problem som knapsack. Vi observerar att det förväntade värdet är otillräckligt för att fånga olika typer av risk-averse eller risk-bene beteenden, och istället anser vi ett mer allmänt mål som är att maximera den förväntade nyttan av lösningen för vissa givna nyttofunktion, snarare än den förväntade vikten (förväntad vikt blir ett specialfall). Under antagandet att det finns en pseudopolynomisk tid algoritm för den exakta versionen av problemet (Detta gäller för de problem som nämns ovan), 1 kan vi få följande approximativa resultat för flera viktiga klasser av nyttofunktioner: 1. Om bruksfunktionen μ är kontinuerlig, övre-bundet av en konstant och lim x→+∞ μ(x) = 0, visar vi att vi kan få en polynom tid approximation algoritm med ett additivt fel för varje konstant > 0. 2. Utgångspunkten är följande: Om bruksfunktionen μ är en konkava ökande funktion, kan vi få en polynom tid approximation schema (PTAS). 3. Vad är det som händer? Om bruksfunktionen μ ökar och har ett avgränsat derivat, kan vi få en polynom tid approximation schema. Våra resultat återhämta eller generalisera flera tidigare resultat på stochastic kortaste vägen, stochastic spanning träd, och stochastic knapsack. Vår algoritm för verktygsmaximering använder sig av separerbarheten av exponentiell nytta och en teknik för att bryta ner en allmän nyttofunktion till exponentiella nyttofunktioner, som kan vara användbara i andra stokastiska optimeringsproblem.
För allmänna diskreta distributioner erhöll Li och Deshpande REF en additiv PTAS om den deterministiska versionen av problemet kan lösas exakt på pseudopolynomisk tid.
Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}