Euclidean TSP with few inner points in linear space

2014/06/09 by Pawel Gawrychowski, Gawrychowski, Pawel, Damian Rusak +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1406.2154

under submission

arxiv created 2014/06/09 · arxiv updated 2014/06/10

Abstract

Given a set of n points in the Euclidean plane, such that just k points are strictly inside the convex hull of the whole set, we want to find the shortest tour visiting every point. The fastest known algorithm for the version when k is significantly smaller than n, i.e., when there are just few inner points, works in O(k^11√(k) k^1.5 n³) time [Knauer and Spillner, WG 2006], but also requires space of order k^c√(k)n². The best linear space algorithm takes O(k! k n) time [Deineko, Hoffmann, Okamoto, Woeginer, Oper. Res. Lett. 34(1), 106-110]. We construct a linear space O(nk²+k^O(√(k))) time algorithm. The new insight is extending the known divide-and-conquer method based on planar separators with a matching-based argument to shrink the instance in every recursive call. This argument also shows that the problem admits a quadratic bikernel.

Related

• A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
• The traveling salesman problem for lines and rays in the plane
• New Approximation Algorithms for Touring Regions
• A PTAS for TSP with Neighborhoods Among Fat Regions in the Plane
• A New Algorithm for Euclidean Shortest Paths in the Plane