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

DOI10.1287/moor.21.2.257zbMath0857.90055OpenAlexW4235273215MaRDI 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

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22) Combinatorial optimization (90C27) Stochastic systems in control theory (general) (93E03)

Related Items (35)

Index-based policies for discounted multi-armed bandits on parallel machines. ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ Sequencing unreliable jobs on parallel machines ⋮ Conditions for indexability of restless bandits and an algorithm to compute Whittle index ⋮ Open Bandit Processes with Uncountable States and Time-Backward Effects ⋮ Optimistic Gittins Indices ⋮ A Polyhedral Approach to Online Bipartite Matching ⋮ Four proofs of Gittins' multiarmed bandit theorem ⋮ On the optimal allocation of service to impatient tasks ⋮ The multi-armed bandit, with constraints ⋮ The archievable region method in the optimal control of queueing systems; formulations, bounds and policies ⋮ Simulation-based optimization of Markov decision processes: an empirical process theory approach ⋮ Search and rescue in the face of uncertain threats ⋮ Index policy for multiarmed bandit problem with dynamic risk measures ⋮ Dynamic Relaxations for Online Bipartite Matching ⋮ Decomposable Markov Decision Processes: A Fluid Optimization Approach ⋮ Bayesian persuasion: reduced form approach ⋮ A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits ⋮ Optimal schedule of elective surgery operations subject to disruptions by emergencies ⋮ A conservative index heuristic for routing problems with multiple heterogeneous service facilities ⋮ THE ECONOMICS OF ATTENTION: MAXIMIZING USER VALUE IN INFORMATION-RICH ENVIRONMENTS ⋮ Dynamic priority allocation via restless bandit marginal productivity indices ⋮ 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 ⋮ A generalized Gittins index for a Markov chain and its recursive calculation ⋮ Submodular function minimization ⋮ A polyhedral approach to online bipartite matching ⋮ Efficiency in lung transplant allocation strategies ⋮ Resource competition in virtual network embedding ⋮ Running Errands in Time: Approximation Algorithms for Stochastic Orienteering ⋮ Unnamed Item ⋮ Dynamic node packing ⋮ QRF ⋮ Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges ⋮ A Restless Bandit Model for Resource Allocation, Competition, and Reservation

This page was built for publication: Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems