Vi studerar flera stokastiska kombinatoriska problem, inklusive den förväntade nytta maximering problem, den stokastiska knapsack problem och den stokastiska bin förpackning problem. En vanlig teknisk utmaning i dessa problem är att optimera någon funktion (annat än förväntan) av summan av en uppsättning slumpmässiga variabler. Svårigheten beror främst på att sannolikhetsfördelningen av summan är konvolutionen av en uppsättning fördelningar, vilket inte är en enkel objektiv funktion att arbeta med. För att ta itu med denna svårighet inför vi Poissons approximationsteknik. Tekniken är baserad på Poisson approximation teorem upptäckt av Le Cam, vilket gör att vi kan approximera fördelningen av summan av en uppsättning slumpmässiga variabler med hjälp av en förening Poisson distribution. Med hjälp av tekniken kan vi reducera en mängd olika stokastiska problem till motsvarande deterministiska multiobjektiva problem, som antingen kan lösas genom standard dynamisk programmering eller har kända lösningar i litteraturen. För de problem som nämns ovan får vi följande resultat: 1. Vi studerar först det förväntade problem med maximering av nytta som nyligen införts [Li och Despande, FOCS11]. För monotona och Lipschitz allmännyttiga funktioner får vi en additiv PTAS om det finns en multidimensionell PTAS för den multi-objektiva versionen av problemet, strikt generalisera det tidigare resultatet. Resultatet innebär den första additiven PTAS för att maximera tröskelsannolikheten för de stokastiska versionerna av global mincut, matroid bas och matroid skärningspunkt. 2. Utgångspunkten är följande: För den stokastiska bin förpackning problem (introduced i [Kleinberg, Rabani och Tardos, STOC97]), visar vi att det finns en polynom tid algoritm som använder högst det optimala antalet bins, om vi slappna av storleken på varje bin och överflödet sannolikhet med  på alla konstant  på > 0. Baserat på detta resultat, vi få en 3- approximation om bara storleken på varje bin kan avslappas av., förbättra den kända O(1/ på) faktor för konstant överflöd sannolikhet. 3. Vad är det som händer? För stokastisk knapsack, visar vi en (1+ på) - approximation med hjälp av  en extra kapacitet för någon  på > 0, även när storleken och belöningen för varje vara kan korreleras och kanBevilja att göra digitala eller hårda kopior av hela eller en del av detta arbete för personligt eller klassrum användning beviljas utan avgift förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga citering på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Celler av objekt är tillåtna. Detta generaliserar det tidigare arbetet [Balghat, Goel och Khanna, SODA11] för fallet utan korrelation och annullering. Vår algoritm är också enklare. Vi presenterar också en faktor 2 +  på approximationsalgoritm för stokastisk knapsack med avbokningar, för alla konstant  till > 0, förbättra den nuvarande kända approximationsfaktorn 8 [Gupta, Krishnaswamy, Molinaro och Ravi, FOCS11]. 4. Vad är det som händer? Vi studerar också en intressant variant av det stokastiska knapsack problemet, där storleken och vinsten av varje vara avslöjas innan beslutet fattas. Problemet faller inom ramen för Bayesian online urvalsproblem, som har studerats en hel del nyligen.
Nyligen, Li och Yuan REF visade att en additiv PTAS för μ  på C begränsas kan erhållas med en helt annan metod, kallas Poisson approximation teknik.
Stochastic combinatorial optimization via poisson approximation
{'venue': "STOC '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}