Tata Institute of Fundamental Research
How Easy/Hard it is to Schedule in Networks?
Student Seminar
Speaker:
Karthyek Rajhaa A M
Organiser:
Sagnik Mukhopadhyay
Date:
Friday, 24 May 2013, 14:30 to 16:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Karthyek Rajhaa A M |
| Organiser: | Sagnik Mukhopadhyay |
| Date: | Friday, 24 May 2013, 14:30 to 16:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.