Title: Charlemagne's challenge: the periodic latency problem
Authors: Coene, Sofie ×
Spieksma, Frederik
Woeginger, G. #
Issue Date: 2011
Publisher: Operations Research Society of America
Series Title: Operations Research vol:59 issue:3 pages: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 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.
ISSN: 0030-364X
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
Charlemagne'sChallenge.pdf Published 294KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science