How Easy/Hard it is to Schedule in Networks?



Friday, 24 May 2013, 14:30 to 16:00


  • A-212 (STCS Seminar Room)


In the context of scheduling in networks, we have the famous max-weight scheduling policy whicminimizes delays, but is computationally intensive for large networks. We also have policies that are computationally nice but offer no guarantees on delays. The question now is:  Can we have a poly time computable scheduling policy that achieves "low" delays? We shall answer this by considering two useful models of communication networks: the independent set constraints model and the SINR model.

Reference: Devavrat Shah, David N. C. Tse, and John N. Tsitsiklis. 2011. Hardness of Low Delay Network Scheduling. IEEE Trans. Inf. Theor. 57, 12 (December 2011), 7810-7817.