Remote Matching: Exact-Cardinality Approximation and Tight UGC Hardness
En palabras de los autores
In the unrestricted max--min metric -join problem, one seeks an even terminal set maximizing the cost of a minimum -join. Iwata and Ravi gave a factor- 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 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 \(\rho(p)\)-approximation for every feasible cardinality, where \[ \rho(p)= \begin{cases} 7/2, & \makebox[1.5em][r]{}<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.
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.