Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
From MaRDI portal
Publication:5495044
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
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