Charlemagne's Challenge: The Periodic Latency Problem

Sofie Coene (), Frits C. R. Spieksma () and Gerhard J. Woeginger ()
Additional contact information
Sofie Coene: Operations Research Group, Katholieke Universiteit Leuven, B-3000 Leuven, Belgium
Frits C. R. Spieksma: Operations Research Group, Katholieke Universiteit Leuven, B-3000 Leuven, Belgium
Gerhard J. Woeginger: Department of Mathematics, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands

Operations Research, 2011, vol. 59, issue 3, 674-683

Abstract: 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 q i 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 q i s. 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.

Keywords: latency problem; periodicity; complexity (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0919 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:59:y:2011:i:3:p:674-683

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().