Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: extended abstract

DOI10.1137/1.9781611973402.85MaRDI QIDQ5384047zbMATH OpenOpenAlexFDO

Authors Will Ma

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973402.85

Mathematics Subject Classification ID

Approximation algorithms (68W25) Stochastic programming (90C15) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Probabilistic games; gambling (91A60)

Recommendations

• Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms
• Approximation algorithms for budgeted learning problems
• Improved approximation results for stochastic knapsack problems
• Bandits with knapsacks
• Approximation algorithms for restless bandit problems

Cited in

(18)

• Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem
• A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes
• Approximation algorithms for stochastic combinatorial optimization problems
• Generalized Restless Bandits and the Knapsack Problem for Perishable Inventories
• Approximation algorithms for budgeted learning problems
• Bandits with knapsacks
• Relaxation analysis for the dynamic knapsack problem with stochastic item sizes
• Stochastic unsplittable flows
• Stochastic graph exploration
• Approximation algorithms for stochastic k-TSP
• Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms
• Submodular maximization with uncertain knapsack capacity
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• Stochastic graph exploration with limited resources
• Approximation algorithms for correlated knapsack orienteering
• On the adaptivity gap of stochastic orienteering

This page was built for publication: Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: extended abstract

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