The Traveling Salesman Problem under squared Euclidean distances

M.T. Berg, de, F.S.B. Nijnatten, van, R.A. Sitters, G.J. Woeginger, A. Wolff

Onderzoeksoutput: Boek/rapportRapportAcademic

2 Citaten (Scopus)

Samenvatting

Let P be a set of points in Rd, and let a = 1 be a real number. We define the distance between two points p, q ¿ P as |pq|a, where |pq| denotes the standard Euclidean distance between p and q. We denote the traveling salesman problem under this distance function by Tsp(d,a). We design a 5-approximation algorithm for Tsp(2,2) and generalize this result to obtain an approximation factor of 3a-1 +v6a/3 for d = 2 and all a = 2. We also study the variant Rev-Tsp of the problem where the traveling salesman is allowed to revisit points. We present a polynomial-time approximation scheme for Rev-Tsp(2, a) with a = 2, and we show that Rev-Tsp(d,a) is apx-hard if d = 3 and a > 1. The apx-hardness proof carries over to Tsp(d, a) for the same parameter ranges.
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's12
StatusGepubliceerd - 2010

Publicatie series

NaamarXiv.org [cs.CG]
Volume1001.0236

Vingerafdruk Duik in de onderzoeksthema's van 'The Traveling Salesman Problem under squared Euclidean distances'. Samen vormen ze een unieke vingerafdruk.

Citeer dit