Preprint
Sep 2026
Remote Matching: Exact-Cardinality Approximation and Tight UGC Hardness
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 stri...
A. Ahadi, Morteza Alimi, Sharareh Alipour et al.
· 0 citations