%AChen, Yu%AKannan, Sampath%AKhanna, Sanjeev%BJournal Name: Leibniz international proceedings in informatics; Journal Volume: 168
%D2020%I
%JJournal Name: Leibniz international proceedings in informatics; Journal Volume: 168
%K
%MOSTI ID: 10185976
%PMedium: X; Size: 30:0 - 30:18
%TSublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
%XWe consider the problem of designing sublinear time algorithms for estimating the cost of minimum] metric traveling salesman (TSP) tour. Specifically, given access to a n × n distance matrix D that specifies pairwise distances between n points, the goal is to estimate the TSP cost by performing only sublinear (in the size of D) queries. For the closely related problem of estimating the weight of
a metric minimum spanning tree (MST), it is known that for any epsilon > 0, there exists an O^~(n/epsilon^O(1))-time algorithm that returns a (1+epsilon)-approximate estimate of the MST cost. This result immediately
implies an O^~(n/epsilon^O(1)) time algorithm to estimate the TSP cost to within a (2 + epsilon) factor for any
epsilon > 0. However, no o(n^2)-time algorithms are known to approximate metric TSP to a factor that is
strictly better than 2. On the other hand, there were also no known barriers that rule out existence of (1 + epsilon)-approximate estimation algorithms for metric TSP with O^~ (n) time for any fixed epsilon > 0. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost.
On the algorithmic side, we first consider the graphic TSP problem where the metric D corresponds to shortest path distances in a connected unweighted undirected graph. We show that there exists an O^~(n) time algorithm that estimates the cost of graphic TSP to within a factor of (2 − epsilon_0) for some epsilon_0 > 0. This is the first sublinear cost estimation algorithm for graphic TSP that
achieves an approximation factor less than 2. We also consider another well-studied special case of metric TSP, namely, (1, 2)-TSP where all distances are either 1 or 2, and give an O^~(n ^ 1.5) time algorithm to estimate optimal cost to within a factor of 1.625. Our estimation algorithms for graphic
TSP as well as for (1, 2)-TSP naturally lend themselves to O^~(n) space streaming algorithms that give an 11/6-approximation for graphic TSP and a 1.625-approximation for (1, 2)-TSP. These results
motivate the natural question if analogously to metric MST, for any epsilon > 0, (1 + epsilon)-approximate
estimates can be obtained for graphic TSP and (1, 2)-TSP using O^~ (n) queries. We answer this
question in the negative – there exists an epsilon_0 > 0, such that any algorithm that estimates the cost of
graphic TSP ((1, 2)-TSP) to within a (1 + epsilon_0)-factor, necessarily requires
(n^2) queries. This lower bound result highlights a sharp separation between the metric MST and metric TSP problems. Similarly to many classical approximation algorithms for TSP, our sublinear time estimation algorithms utilize subroutines for estimating the size of a maximum matching in the underlying
graph. We show that this is not merely an artifact of our approach,
and that for any epsilon > 0, any
algorithm that estimates the cost of graphic TSP or (1, 2)-TSP to within a (1 + epsilon)-factor, can also
be used to estimate the size of a maximum matching in a bipartite graph to within an epsilon n additive
error. This connection allows us to translate known lower bounds for matching size estimation in
various models to similar lower bounds for metric TSP cost estimation.
%0Journal Article