Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems

DOI10.1287/moor.21.2.257zbMath0857.90055MaRDI QIDQ4895559

José Niño-Mora, Dimitris J. Bertsimas

Publication date: 14 October 1996

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

Full work available at URL: https://doi.org/10.1287/moor.21.2.257

zbMATH Keywords

performance measures; adaptive greedy algorithm; extended polymatroid; Gittins indices; multiarmed bandit; generalized conservation laws; decomposable systems; indexability property; indexable systems; stochastic and dynamic scheduling

Mathematics Subject Classification ID

90C05: Linear programming

90B35: Deterministic scheduling theory in operations research

60K25: Queueing theory (aspects of probability theory)

90B22: Queues and service in operations research

90C27: Combinatorial optimization

93E03: Stochastic systems in control theory (general)

Related Items

Unnamed Item, On the optimal allocation of service to impatient tasks, A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits, Running Errands in Time: Approximation Algorithms for Stochastic Orienteering, QRF, Open Bandit Processes with Uncountable States and Time-Backward Effects, Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges, Approximation algorithms for stochastic combinatorial optimization problems, Four proofs of Gittins' multiarmed bandit theorem, The multi-armed bandit, with constraints, Solving convex optimization with side constraints in a multi-class queue by adaptive \(c\mu \) rule, Stochastic scheduling: a short history of index policies and new approaches to index generation for dynamic resource allocation, Simulation-based optimization of Markov decision processes: an empirical process theory approach, Sequencing unreliable jobs on parallel machines, Dynamic priority allocation via restless bandit marginal productivity indices, A generalized Gittins index for a Markov chain and its recursive calculation, Submodular function minimization, A polyhedral approach to online bipartite matching, Index-based policies for discounted multi-armed bandits on parallel machines., The archievable region method in the optimal control of queueing systems; formulations, bounds and policies, Search and rescue in the face of uncertain threats, Decomposable Markov Decision Processes: A Fluid Optimization Approach, A Polyhedral Approach to Online Bipartite Matching, THE ECONOMICS OF ATTENTION: MAXIMIZING USER VALUE IN INFORMATION-RICH ENVIRONMENTS