An Improved Upper Bound for the Universal TSP on the Grid



Christodoulou, G and Sgouritsa, A
(2017) An Improved Upper Bound for the Universal TSP on the Grid. In: Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona.

This is the latest version of this item.

[img] Text
tspForN.pdf - Author Accepted Manuscript

Download (1MB)

Abstract

We study the universal Traveling Salesman Problem in an n × n grid with the shortest path metric. The goal is to define a (universal) total ordering over the set of grid's vertices, in a way that for any input (subset of vertices), the tour, which visits the points in this ordering, is a good approximation of the optimal tour, i.e. has low competitive ratio. This problem was first studied by Platzman and Bartholdi [26]. They proposed a heuristic, which was based on the Sierpinski space-filling curve, in order to define a universal ordering of the unit square [0; 1]2 under the Euclidean metric. Their heuristic visits the points of the unit square in the order of their appearance along the space-filling curve. They provided a logarithmic upper bound which was shown to be tight up to a constant by Bertsimas and Grigni [3]. Bertsimas and Grigni further showed logarithmic lower bounds for other space-filling curves and they conjectured that any universal ordering has a logarithmic lower bound for the n × n grid. In this work, we disprove this conjecture by showing that there exists a universal ordering of the n n grid with competitive ratio of O . The heuristic we propose defines a universal ordering of the grid's vertices based on a generalization of the Lebesgue space- filling curve. In order to analyze the competitive ratio of our heuristic, we employ techniques from the theory of geometric spanners in Euclidean spaces. We finally show that our analysis is tight up to a constant.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 26 Jun 2017 10:14
Last Modified: 19 Jan 2023 07:03
DOI: 10.1137/1.9781611974782.64
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007923

Available Versions of this Item