Charlemagne's challenge : the periodic latency problem

S. Coene, F.C.R. Spieksma, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

7 Citaten (Scopus)
1 Downloads (Pure)


Latency problems are characterized by their focus on minimizing the waiting time for all clients. We study periodic latency problems, a nontrivial extension of standard latency problems. In a periodic latency problem each client has to be visited regularly: there is a server traveling at unit speed, and there is a set of n clients with given positions. The server must visit the clients over and over again, subject to the constraint that successive visits to client i are at most qi time units away from each other. We investigate two main problems. In problem PLPP the goal is to find a repeatable route for the server visiting as many clients as possible without violating their qis. In problem PLP the goal is to minimize the number of servers needed to serve all clients. Depending on the topology of the underlying network, we derive polynomial-time algorithms or hardness results for these two problems. Our results draw sharp separation lines between easy and hard cases.
Originele taal-2Engels
Pagina's (van-tot)674-683
Aantal pagina's10
TijdschriftOperations Research
Nummer van het tijdschrift3
StatusGepubliceerd - 2011


Duik in de onderzoeksthema's van 'Charlemagne's challenge : the periodic latency problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit