Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

DOI10.1109/FOCS.2011.48MaRDI QIDQ5495044zbMATH OpenOpenAlexFDO

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

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

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

Cited in

(30)

• Submodular maximization with uncertain knapsack capacity
• Relaxation analysis for the dynamic knapsack problem with stochastic item sizes
• Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
• Stochastic graph exploration with limited resources
• Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem
• Stochastic unsplittable flows
• Approximation algorithms for stochastic combinatorial optimization problems
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• scientific article; zbMATH DE number 7053373 (Why is no real title available?)
• Submodular stochastic probing on matroids
• Constrained stochastic submodular maximization with state-dependent costs
• Adaptive Bin Packing with Overflow
• 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 knapsack revisited: the service level perspective
• Stochastic graph exploration
• On the adaptivity gap of stochastic orienteering
• Approximation algorithms for stochastic \(k\)-TSP
• The benefit of adaptivity in stochastic packing problems with probing
• Stochastic submodular probing with state-dependent costs
• Stochastic submodular probing with state-dependent costs
• Configuration balancing for stochastic requests
• Approximability of the two-stage stochastic knapsack problem with discretely distributed weights
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• Unrelated machine scheduling with stochastic processing times
• Stochastic minimum vertex cover in general graphs: a \(3/2\)-approximation
• Adaptivity in the stochastic blackjack knapsack problem
• Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms
• Adversarial bandits with knapsacks
• Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495044)