The complexity of optimal queueing network control
Christos H. Papadimitriou, John N. Tsitsiklis · 2002
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.>