1
$\begingroup$

What is the current best (in terms of running time) (1+\epsilon)-approximation algorithm (both randomized and deterministic) for non-bipartite Euclidean (in higher dimension) matching? There are recent works on the bipartite version (as for instance https://arxiv.org/pdf/2204.03875.pdf). Among the non-bipartite, I have found a relatively earlier result of Vardarajan & Aggarwal (https://www2.cs.arizona.edu/~alon/papers/approx-match.pdf) which works only in the Euclidean plane. Is there any improved algorithm?

Improve this question
$\endgroup$
1
  • $\begingroup$ Further what is the status on the doubling metric? $\endgroup$
    – Sandip
    Feb 19 at 19:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.