Remote Matching: Exact-Cardinality Approximation and Tight UGC Hardness

Arash Ahadi, Morteza Alimi, Sharareh Alipour +1

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…