文章基本信息
- 标题：Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
- 本地全文：下载
- 作者：Yu Chen ; Sampath Kannan ; Sanjeev Khanna 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：168
- 页码：30:1-30:19
- DOI：10.4230/LIPIcs.ICALP.2020.30
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：We 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 ε > 0, there exists an OÌf(n/ε^O(1)) time algorithm that returns a (1 + ε)-approximate estimate of the MST cost. This result immediately implies an OÌf(n/ε^O(1)) time algorithm to estimate the TSP cost to within a (2 + ε) factor for any ε > 0. However, no o(n²) 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 + ε)-approximate estimation algorithms for metric TSP with OÌf(n) time for any fixed ε > 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Ìf(n) time algorithm that estimates the cost of graphic TSP to within a factor of (2-εâ,) for some εâ, > 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Ìf(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Ìf(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 ε > 0, (1 + ε)-approximate estimates can be obtained for graphic TSP and (1,2)-TSP using OÌf(n) queries. We answer this question in the negative - there exists an εâ, > 0, such that any algorithm that estimates the cost of graphic TSP ((1,2)-TSP) to within a (1 + εâ,)-factor, necessarily requires Ω(n²) 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 ε > 0, any algorithm that estimates the cost of graphic TSP or (1,2)-TSP to within a (1 + ε)-factor, can also be used to estimate the size of a maximum matching in a bipartite graph to within an ε 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.
- 关键词：sublinear algorithms; TSP; streaming algorithms; query complexity
