Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

DOI10.1109/FOCS.2011.48zbMath1292.90216OpenAlexW2006618115MaRDI QIDQ5495044

Ravishankar Krishnaswamy, Anupam Gupta, R. Ravi, Marco Molinaro

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.48

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (28)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ Submodular Stochastic Probing on Matroids ⋮ Stochastic Knapsack Revisited: The Service Level Perspective ⋮ Adaptivity in the stochastic blackjack knapsack problem ⋮ Configuration balancing for stochastic requests ⋮ On the adaptivity gap of stochastic orienteering ⋮ Constrained stochastic submodular maximization with state-dependent costs ⋮ Unnamed Item ⋮ Stochastic graph exploration with limited resources ⋮ Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards ⋮ Approximability of the two-stage stochastic knapsack problem with discretely distributed weights ⋮ The benefit of adaptivity in stochastic packing problems with probing ⋮ Stochastic Unsplittable Flows ⋮ Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem ⋮ Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ Stochastic submodular probing with state-dependent costs ⋮ Stochastic submodular probing with state-dependent costs ⋮ Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms ⋮ Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ Stochastic graph exploration ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ Unnamed Item ⋮ Running Errands in Time: Approximation Algorithms for Stochastic Orienteering ⋮ Unnamed Item ⋮ Adaptive Bin Packing with Overflow

This page was built for publication: Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits