Tuesday, 15:45 - 16:10 h, Room: MA 376


Ramamoorthi Ravi
Approximation algorithms for correlated knapsacks and non-martingale bandits

Coauthors: Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro


We give constant-factor approximation algorithms for the stochastic knapsack problem with correlations and cancelations, and also for some budgeted learning problems where the martingale condition is not satisfied, using similar ideas. Indeed, we can show that previously proposed linear programming relaxations for these problems have large integrality gaps. We propose new time-indexed LP relaxations; using a decomposition and "shifting'' approach, we convert these fractional solutions to distributions over strategies, and then use the LP values and the time ordering information from these strategies to devise a randomized scheduling algorithm. We hope our LP formulation and decomposition methods may provide a new way to address other correlated bandit problems with more general contexts.
The paper is available at, http://arxiv.org/abs/1102.3749


Talk 2 of the invited session Tue.3.MA 376
"Approximation algorithms for stochastic combinatorial optimization" [...]
Cluster 22
"Stochastic optimization" [...]


  The main criterion for them is your ability to repay any Payday Loans In Wisconsin, they are not interested in your previous attempts, the current one is all that matters. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.