School of Technology and Computer Science Seminars

How Easy/Hard it is to Schedule in Networks?

by Mr. Karthyek Rajhaa A.M. (School of Technology and Computer Science, TIFR)

Friday, May 24, 2013 from to (Asia/Kolkata)
at Colaba Campus ( A-212 (STCS Seminar Room) )
Description
In the context of scheduling in networks, we have the famous max-weight scheduling policy which minimizes 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.