DocumentCode
1992267
Title
The complexity of optimal queueing network control
Author
Papadimitriou, Christos H. ; Tsitsiklis, John N.
Author_Institution
California Univ., San Diego, La Jolla, CA, USA
fYear
1994
fDate
28 Jun- 1 Jul 1994
Firstpage
318
Lastpage
322
Abstract
We consider the classical problem of optimal control (routing and sequencing) of a network of queues. We prove that this problem is EXP-complete and, therefore, provably intractable. Similar results are established for restricted versions of the problem. A weaker result is also established for the restless bandit problem
Keywords
computational complexity; optimal control; queueing theory; EXP-complete; complexity; optimal control; optimal queueing network control; restless bandit problem; Application software; Complex networks; Logic; Network servers; Optimal control; Probability distribution; Routing; Steady-state; Throughput; Time measurement;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location
Amsterdam
Print_ISBN
0-8186-5670-0
Type
conf
DOI
10.1109/SCT.1994.315792
Filename
315792
Link To Document