Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

DOI10.1109/FOCS.2011.48zbMATH Open1292.90216OpenAlexW2006618115MaRDI QIDQ5495044FDOQ5495044

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)

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation algorithms for stochastic combinatorial optimization problems
• Constrained stochastic submodular maximization with state-dependent costs
• Adaptive Bin Packing with Overflow
• Submodular stochastic probing on matroids
• A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes
• Stochastic knapsack revisited: the service level perspective
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Stochastic graph exploration
• Approximation algorithms for stochastic \(k\)-TSP
• On the adaptivity gap of stochastic orienteering
• Stochastic submodular probing with state-dependent costs
• Stochastic submodular probing with state-dependent costs
• The benefit of adaptivity in stochastic packing problems with probing
• 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
• Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms
• Adversarial bandits with knapsacks
• Adaptivity in the stochastic blackjack knapsack problem
• Submodular maximization with uncertain knapsack capacity
• Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes
• Relaxation analysis 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)