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.
