Charlemagne's challenge : the periodic latency problem

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

doi:10.1109/IEEM.2009.5373358

Charlemagne's challenge : the periodic latency problem

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management (IEEM'09, Hong Kong, December 8-11, 2009)
Publisher	Institute of Electrical and Electronics Engineers
Pages	296-300
ISBN (Print)	978-1-4244-4869-2
DOIs	https://doi.org/10.1109/IEEM.2009.5373358
Publication status	Published - 2009
Event	2009 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM 2009) - Hong Kong, Hong Kong Duration: 8 Dec 2009 → 11 Dec 2009 Conference number: 2009

Conference

Conference	2009 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM 2009)
Abbreviated title	IEEM
Country	Hong Kong
City	Hong Kong
Period	8/12/09 → 11/12/09

Access to Document

10.1109/IEEM.2009.5373358

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

Cite this

@inproceedings{d8569a325c454ef68d317c3b0af51568,

title = "Charlemagne's challenge : the periodic latency problem",

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.",

author = "S. Coene and G.J. Woeginger and F.C.R. Spieksma",

year = "2009",

doi = "10.1109/IEEM.2009.5373358",

language = "English",

isbn = "978-1-4244-4869-2",

pages = "296--300",

booktitle = "Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management (IEEM'09, Hong Kong, December 8-11, 2009)",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "2009 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM 2009), IEEM ; Conference date: 08-12-2009 Through 11-12-2009",

}

Coene, S, Woeginger, GJ & Spieksma, FCR 2009, Charlemagne's challenge : the periodic latency problem. in Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management (IEEM'09, Hong Kong, December 8-11, 2009). Institute of Electrical and Electronics Engineers, pp. 296-300, 2009 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM 2009), Hong Kong, Hong Kong, 8/12/09. https://doi.org/10.1109/IEEM.2009.5373358

Charlemagne's challenge : the periodic latency problem. / Coene, S.; Woeginger, G.J.; Spieksma, F.C.R.

Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management (IEEM'09, Hong Kong, December 8-11, 2009). Institute of Electrical and Electronics Engineers, 2009. p. 296-300.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Charlemagne's challenge : the periodic latency problem

AU - Coene, S.

AU - Woeginger, G.J.

AU - Spieksma, F.C.R.

N1 - Conference code: 2009

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1109/IEEM.2009.5373358

DO - 10.1109/IEEM.2009.5373358

M3 - Conference contribution

SN - 978-1-4244-4869-2

SP - 296

EP - 300

BT - Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management (IEEM'09, Hong Kong, December 8-11, 2009)

PB - Institute of Electrical and Electronics Engineers

T2 - 2009 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM 2009)

Y2 - 8 December 2009 through 11 December 2009

ER -