Charlemagne's challenge : the periodic latency problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the IEEE International Conference on Industrial Engineering and Engineering Management (IEEM'09, Hong Kong, December 8-11, 2009)
PublisherInstitute of Electrical and Electronics Engineers
Pages296-300
ISBN (Print)978-1-4244-4869-2
DOIs
Publication statusPublished - 2009
Event2009 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM 2009) - Hong Kong, Hong Kong
Duration: 8 Dec 200911 Dec 2009
Conference number: 2009

Conference

Conference2009 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM 2009)
Abbreviated titleIEEM
CountryHong Kong
CityHong Kong
Period8/12/0911/12/09

Fingerprint Dive into the research topics of 'Charlemagne's challenge : the periodic latency problem'. Together they form a unique fingerprint.

Cite this