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" [...]


  Payday Loans In Virginia. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Levitra Online, but also as part of its analogs.