The Complexity of Optimal Queuing Network Control

DOI10.1287/moor.24.2.293zbMath0977.90008OpenAlexW2105556121MaRDI QIDQ2757596

John N. Tsitsiklis, Christos H. Papadimitriou

Publication date: 26 November 2001

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

Full work available at URL: https://semanticscholar.org/paper/3808e63d89b6a251f37cb19d7761e3e037e4897b

zbMATH Keywords

computational complexityoptimal controlqueueing network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Queues and service in operations research (90B22) Optimal stochastic control (93E20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20)

Related Items (42)

Conditions for indexability of restless bandits and an algorithm to compute Whittle index ⋮ Optimal selection of obsolescence mitigation strategies using a restless bandit model ⋮ Scalable Reinforcement Learning for Multiagent Networked Systems ⋮ Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic ⋮ Approximate linear programming for networks: average cost bounds ⋮ Dynamic routing in distinguishable parallel queues: an application of product returns for remanufacturing ⋮ Scheduling of multi-class multi-server queueing systems with abandonments ⋮ Whittle’s Index Policy for Multi-Target Tracking with Jamming and Nondetections ⋮ Sensor Scheduling for Space Object Tracking and Collision Alert ⋮ A fluid approach to large volume job shop scheduling ⋮ On the computation of Whittle's index for Markovian restless bandits ⋮ Multi-machine preventive maintenance scheduling with imperfect interventions: a restless bandit approach ⋮ INDEXABILITY AND OPTIMAL INDEX POLICIES FOR A CLASS OF REINITIALISING RESTLESS BANDITS ⋮ Algorithms and mechanisms for procuring services with uncertain durations using redundancy ⋮ Exponential asymptotic optimality of Whittle index policy ⋮ Index policies for discounted bandit problems with availability constraints ⋮ A mean field approach for optimization in discrete time ⋮ A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits ⋮ Prioritizing Hepatitis C Treatment in U.S. Prisons ⋮ Optimal scheduling of multiple sensors over shared channels with packet transmission constraint ⋮ Dynamic priority allocation via restless bandit marginal productivity indices ⋮ Group Maintenance: A Restless Bandits Approach ⋮ Nonstationary Bandits with Habituation and Recovery Dynamics ⋮ Some indexable families of restless bandit problems ⋮ An Approximation Approach for Response-Adaptive Clinical Trial Design ⋮ An Overview for Markov Decision Processes in Queues and Networks ⋮ Unnamed Item ⋮ General notions of indexability for queueing control and asset management ⋮ Exponential penalty function control of loss networks ⋮ Index policies for the maintenance of a collection of machines by a set of repairmen ⋮ An asymptotically optimal heuristic for general nonstationary finite-horizon restless multi-armed, multi-action bandits ⋮ Grid Brokering for Batch Allocation Using Indexes ⋮ Spinning plates and squad systems: policies for bi-directional restless bandits ⋮ Approximations of the Restless Bandit Problem ⋮ Resource competition in virtual network embedding ⋮ Learning, risk attitude and hot stoves in restless bandit problems ⋮ Whittle indexability in egalitarian processor sharing systems ⋮ Unnamed Item ⋮ Time-Constrained Restless Bandits and the Knapsack Problem for Perishable Items (Extended Abstract) ⋮ Performance optimization for a class of generalized stochastic Petri nets ⋮ Whittle index based Q-learning for restless bandits with average reward ⋮ A Restless Bandit Model for Resource Allocation, Competition, and Reservation

This page was built for publication: The Complexity of Optimal Queuing Network Control