arXiv preprint ·
Sublinear-Time and Semi-Streaming Algorithms for Path Cover and TSP
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give improved sublinear-time and semi-streaming approximation algorithms for maximum path cover, $(1,2)$-TSP, and Max-TSP. For each fixed $\eps>0$, our distance-query algorithm estimates the optimum cost of an $n$-vertex $(1,2)$-TSP instance from above within factor $2-\cstar+\eps=1.413184\ldots+\eps$, with high probability, in $n^{2-Ω_\eps(1)}$ time, where $\cstar=2(\sec1-\tan1)$. This improves the $3/2+\eps$ factor of direct matching estimation in this subquadratic regime~\cite{BhattacharyaKissSaranurak2023} and of the faster near-linear estimator~\cite{BehnezhadEtAl2024}. A single random vertex order defines an implicit bipartite graph whose matchings project to path covers. An alternating-permutation analysis shows that its expected maximum matching size is at least $\cstar$ times the optimum path-cover size. On long paths, even the best of polynomially many uniform orders retains only a $\cstar+o(1)$ fraction with high probability. In semi-streaming, we construct deterministic $(5/7-\eps)$-approximate unweighted path covers and $(9/7+\eps+5/(7n))$-approximate $(1,2)$-TSP tours, improving the respective $2/3-\eps$ and $4/3+\eps+1/n$ guarantees in~\cite{AlipourFarokhnejadMoemke2025}. For nonnegative weights, we obtain $2/3-\eps$ for path cover and Max-TSP, improving the earlier asymptotic $7/12-\eps$ Max-TSP bound. These algorithms use $\poly(1/\eps)$ passes independent of $n$ and $O(n\log(n/\eps)\poly(1/\eps))$ words. We compute two approximate matchings separated by edge deletion. A cycle-compensation lemma accounts for the weight removed when breaking their cycles. For unweighted graphs, a third approximate matching on a simple auxiliary graph with at most $2n$ vertices chooses component connections; a Tutte--Berge count proves the stronger bound.
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.