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, Resource competition in virtual network embedding, A Restless Bandit Model for Resource Allocation, Competition, and Reservation, Conditions for indexability of restless bandits and an algorithm to compute Whittle index, Optimistic Gittins Indices, Dynamic Relaxations for Online Bipartite Matching, 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, Index policy for multiarmed bandit problem with dynamic risk measures, Bayesian persuasion: reduced form approach, 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, Efficiency in lung transplant allocation strategies, Dynamic node packing, Search and rescue in the face of uncertain threats, A conservative index heuristic for routing problems with multiple heterogeneous service facilities, Optimal schedule of elective surgery operations subject to disruptions by emergencies, 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