Charlemagne's Challenge: The Periodic Latency Problem

• 成果类型: Article
• 署名作者: Coene, Sofie; Spieksma, Frits C. R.; Woeginger, Gerhard J.
• 署名单位: KU Leuven; Eindhoven University of Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1110.0919
• 发表日期: 2011
• 页码: 674-683
• 关键词: algorithms; CLASSIFICATION

摘要

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.