Charlemagne's challenge: The periodic latency problem

摘要

Latency problems are characterized by their focus on minimizing total waiting time for all clients. We consider periodic latency problems: an extension of standard latency problems. In a periodic latency problem each client has to be visited regularly. More precisely, given is a server traveling at unit speed, and a set of clients with their positions. To each client a periodicity is associated that is the maximal amount of time that is allowed to pass between consecutive visits of the server to that client. In a problem we denote as PLPP, the goal is then to find a repeatable route for the server visiting as many clients as possible without violating the periodicities. Further, we consider the PLP in which the number of servers needed to serve all clients is minimized. We give polynomial-time algorithms and NP-hardness results for these problems depending upon the topology of the underlying network.