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 problemsUnrelated Machine Scheduling with Stochastic Processing TimesSubmodular Stochastic Probing on MatroidsStochastic Knapsack Revisited: The Service Level PerspectiveAdaptivity in the stochastic blackjack knapsack problemConfiguration balancing for stochastic requestsOn the adaptivity gap of stochastic orienteeringConstrained stochastic submodular maximization with state-dependent costsUnnamed ItemStochastic graph exploration with limited resourcesLogarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal RewardsApproximability of the two-stage stochastic knapsack problem with discretely distributed weightsThe benefit of adaptivity in stochastic packing problems with probingStochastic Unsplittable FlowsLower bounds on the adaptivity gaps in variants of the stochastic knapsack problemRelaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item SizesA column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizesWhen LP is the cure for your matching woes: improved bounds for stochastic matchingsStochastic submodular probing with state-dependent costsStochastic submodular probing with state-dependent costsImprovements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation AlgorithmsSemi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item SizesStochastic graph explorationSubmodular Maximization with Uncertain Knapsack CapacityUnnamed ItemRunning Errands in Time: Approximation Algorithms for Stochastic OrienteeringUnnamed ItemAdaptive Bin Packing with Overflow




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