Euclidean TSP in narrow strips

Abstract: We investigate how the complexity of Euclidean TSP for point sets

P

inside the strip

(- i n f t y, + i n f t y) i m e s [0, d e l t a]

depends on the strip width

d e l t a

. We obtain two main results. First, for the case where the points have distinct integer

x

-coordinates, we prove that a shortest bitonic tour (which can be computed in

O (n l o g^{2} n)

time using an existing algorithm) is guaranteed to be a shortest tour overall when

d e l t a l e q 2 s q r t 2

, a bound which is best possible. Second, we present an algorithm that is fixed-parameter tractable with respect to

d e l t a

. More precisely, our algorithm has running time

2^{O (s q r t d e l t a)} n^{2}

for sparse point sets, where each

1 i m e s d e l t a

rectangle inside the strip contains

O (1)

points. For random point sets, where the points are chosen uniformly at random from the rectangle~

[0, n] i m e s [0, d e l t a]

, it has an expected running time of

2^{O (s q r t d e l t a)} n^{2} + O (n^{3})

.

Recommendations

Cited in

(2)

This page was built for publication: Euclidean TSP in narrow strips