Hardness Result for Tsp with Neighborhoods
| Author(s) : | Christos Levcopoulos Joachim Gudmundsson, |
| Publisher : | N/A |
| Publication Date : | 2000 |
| ISSN : | N/A |
| Abstract : | Abstract. In TSP with neighborhoods (TSPN) we are given a collection X of k polygonal regions, called neighborhoods, with totally n vertices, and we seek the shortest tour that visits each neighborhood. The Euclidean TSP is a special case of the TSPN problem, so TSPN is also NP-hard. In this paper we show that TSPN also is APX-hard and cannot be approximated within a factor of 1.000374 in polynomial time. 1, |