arXiv preprint ·
Remote Matching: Exact-Cardinality Approximation and Tight UGC Hardness
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In the unrestricted max--min metric $T$-join problem, one seeks an even terminal set $T$ maximizing the cost of a minimum $T$-join. Iwata and Ravi gave a factor-$3/2$ approximation for this problem. We show that this guarantee is tight under the Unique Games Conjecture: no polynomial-time approximation with factor strictly smaller than $3/2$ exists under UGC. We then consider the exact-cardinality variant, which prescribes an even number \(k\) of terminals. Writing \(p:=k/n\), we give a deterministic polynomial-time \(ρ(p)\)-approximation for every feasible cardinality, where \[ ρ(p)= \begin{cases} 7/2, & \makebox[1.5em][r]{$0$}<p\le2/7,\\ 1/p, & 2/7\le p\le2/3,\\ 1/[2(1-p)], & 2/3\le p\le7/8,\\ 4, & 7/8\le p<1. \end{cases} \] In particular, a factor-\(4\) approximation holds throughout the entire feasible cardinality range, the factor is at most \(7/2\) whenever \(0<k\le 6n/7\), and equals \(3/2\) at \(k=2n/3\). The algorithmic framework is based on optimal laminar cut packings, their weighted tree representations, exact-cardinality rounding, and tree dynamic programming.
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
Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation
Improved Algorithms for the Remote Point Problem
$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice
Exponential Quantum Advantage in Testing Fourier Dimensionality
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.