On the Complexity of the Minimum Latency Scheduling Problem on the Euclidean Plane

Henry Lin, Frans Schalekamp

We show NP-hardness of the minimum latency scheduling (MLS) problem under the physical model of wireless networking. In this model a transmission is received successfully if the Si…