Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms

DOI10.1287/moor.2017.0884zbMath1440.90035arXiv1306.1149OpenAlexW2787518409MaRDI QIDQ5219671

Will Ma

Publication date: 12 March 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.1149

zbMATH Keywords

stochastic programmingapproximation algorithmsstochastic knapsackMarkovian multi-armed bandit

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Markov and semi-Markov decision processes (90C40) Approximation algorithms (68W25)

Related Items (6)

Configuration balancing for stochastic requests ⋮ Stochastic Probing with Increasing Precision ⋮ Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards ⋮ An adversarial model for scheduling with testing ⋮ A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes ⋮ Adaptive Bin Packing with Overflow

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• TECHNICAL NOTE—The Adaptive Knapsack Problem with Stochastic Rewards
• Multi‐Armed Bandit Allocation Indices
• The Irrevocable Multiarmed Bandit Problem
• Approximation in stochastic scheduling
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• A Learning Approach for Interactive Marketing to a Customer Segment
• An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns
• Allocating Bandwidth for Bursty Connections
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• On the Adaptivity Gap of Stochastic Orienteering
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Stochastic combinatorial optimization via poisson approximation
• On a Chebyshev-Type Inequality for Sums of Independent Random Variables
• Scheduling

This page was built for publication: Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms