TY - GEN
T1 - The minimum latency problem is NP-hard for weighted trees
AU - Sitters, R.A.
PY - 2002
Y1 - 2002
N2 - 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}.
AB - 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}.
U2 - 10.1007/3-540-47867-1_17
DO - 10.1007/3-540-47867-1_17
M3 - Conference contribution
SN - 3-540-43676-6
T3 - Lecture Notes in Computer Science
SP - 230
EP - 239
BT - Integer Programming and Combinatorial Optimization (Proceedings 9th IPCO, Cambridge MA, USA, May 27-29, 2002)
A2 - Cook, W.J.
A2 - Schulz, A.S.
PB - Springer
CY - Berlin
ER -