arXiv preprint ·
Semi-Streaming Estimation of the Held--Karp Bound and Graph-Metric TSP Cost
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The Held--Karp bound is a linear-programming lower bound for the metric traveling salesperson problem (TSP). We approximate this bound in the multi-pass insertion-only streaming model for metrics induced by connected positive-weight graphs. For an $n$-vertex, $m$-edge graph and $0<\eps\le1/2$, the algorithm returns a $(1+\eps)$ upper approximation with high probability, using $\wtO(\eps^{-4})$ passes, $\wtO(n\eps^{-2})$ words, and $\wtO(m\eps^{-4})$ arithmetic operations per pass. We replace the changing edge-weight vector by a short history of multiplicative-weights (MWU) updates. After initialization, updates repeat until a column is removed. We store each repeated update once, with its repetition count. The record length depends on the number of columns, not updates; the argument applies to any fixed nonnegative matrix. For Held--Karp, tree-path queries recover edge weights from these records. Separate search and update thresholds allow fresh sparsifiers at successive search stages. Controlled rounding gives a bounded-precision implementation. The estimate yields a $(3/2+\eps)$ graph-metric TSP value estimate and a $(7/5+\eps)$ estimate when the input graph is unweighted. Conversely, in weighted graph streams, every one-pass $(1+η)$ upper approximation to Held--Karp, for fixed $0\leη<1$, requires quadratic space. The algorithms estimate values; they do not construct tours within these bounds.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Improved Combinatorial Auctions with and without Samples
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage
Query Complexity of Densest Sub(hyper)graph Problems
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.