Abstract
In the minimum latency problem (MLP) we are given n points v 1,..., v n and a distance d(v i,v j) between any pair of points. We have to find a tour, starting at v 1 and visiting all points, for which the sum of arrival times is minimal. The arrival time at a point v i is the traveled distance from v 1 to v i in the tour. The minimum latency problem is MAX-SNP-hard for general metric spaces, but the complexity for the problem where the metric is given by an edge-weighted tree has been a long-standing open problem. We show that the minimum latency problem is NP-hard for trees even with weights in {0,1}.
| Original language | English |
|---|---|
| Title of host publication | Integer Programming and Combinatorial Optimization (Proceedings 9th IPCO, Cambridge MA, USA, May 27-29, 2002) |
| Editors | W.J. Cook, A.S. Schulz |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 230-239 |
| ISBN (Print) | 3-540-43676-6 |
| DOIs | |
| Publication status | Published - 2002 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 2337 |
| ISSN (Print) | 0302-9743 |
Fingerprint Dive into the research topics of 'The minimum latency problem is NP-hard for weighted trees'. Together they form a unique fingerprint.
Cite this
Sitters, R. A. (2002). The minimum latency problem is NP-hard for weighted trees. In W. J. Cook, & A. S. Schulz (Eds.), Integer Programming and Combinatorial Optimization (Proceedings 9th IPCO, Cambridge MA, USA, May 27-29, 2002) (pp. 230-239). (Lecture Notes in Computer Science; Vol. 2337). Berlin: Springer. https://doi.org/10.1007/3-540-47867-1_17