Abstract-I den stokastiska knapsack problem, får vi en knapsack av storlek B, och en uppsättning objekt vars storlekar och belöningar hämtas från en känd sannolikhetsfördelning. För att veta den faktiska storleken och belöningen måste vi schemalägga objektet-när det avslutas, vi lära känna dessa värden. Målet är att schemalägga objekten (eventuellt fatta adaptiva beslut baserat på de storlekar som hittills setts) för att maximera den förväntade totala belöningen av objekt som framgångsrikt packa in i ryggsäcken. Vi vet konstant-faktor approximationer när (i) belöningar och storlekar är oberoende, och (ii) vi kan inte i förtid avbryta objekt efter att vi schemalagt dem. Vad händer om antingen eller båda antagandena är avslappnade? Relaterade stokastiska förpackningsproblem är multi-armad bandit (och budgeterad inlärning) problem; här får man flera armar som utvecklas på ett specificerat stokastiskt sätt med varje drag, och målet är att (adaptivt) bestämma vilka armar att dra, för att maximera den förväntade belöningen som erhålls efter B drar totalt. Mycket nytt arbete på detta problem fokuserar på fallet när utvecklingen av varje arm följer en martingale, dvs. när den förväntade belöningen från en dra av en arm är samma som belöningen i det nuvarande tillståndet. Vad händer om belöningarna inte bildar en martingale? I den här artikeln ger vi O(1)-tillnärmning algoritmer för stokastiska knapsack problem med korrelationer och / eller avbokningar. Utvidga de idéer som utvecklats här, ger vi O(1)- approximationer för MAB-problem utan martingale antagande. Vi kan faktiskt visa att tidigare föreslagna linjära program avkopplingar för dessa problem har stora integratitetsluckor. Så vi föreslår nya tidsindexerade LP avkopplingar; med hjälp av en nedbrytning och "gapfilling" metod, vi konvertera dessa fraktionerade lösningar till distributioner över strategier, och sedan använda LP-värden och tid beställa information från dessa strategier för att utforma randomiserade adaptiva schemaläggning algoritmer.
Gupta m.fl. REF gav en konstant-faktor approximation för SK-CC baserat på LP avslappning.
Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}