Improved Lower Bounds for the Universal and a priori TSP

We consider two partial-information generalizations of the metric traveling salesman problem (TSP) in which the task is to produce a total ordering of a given metric space that performs well for a subset of the space that is not known in advance. In the universal TSP, the subset is chosen adversarially, and in the TSP it is chosen probabilistically. Both the universal and TSP have been studied since the mid-80’s, starting with the work of Bartholdi & Platzman and Jaillet, respectively. We prove a lower bound of Ω(log

n

) for the universal TSP by bounding the competitive ratio of shortest-path metrics on Ramanujan graphs, which improves on the previous best bound of Hajiaghayi, Kleinberg & Leighton, who showed that the competitive ratio of the

n

×

n

grid is

$\Omega(\sqrt[6]{\log n / \log \log n})$

. Furthermore, we show that for a large class of combinatorial optimization problems that includes TSP, a bound for the universal problem implies a matching bound on the approximation ratio achievable by deterministic algorithms for the corresponding black-box problem. As a consequence, our lower bound of Ω(log

n

) for the universal TSP implies a matching lower bound for the black-box TSP.