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?

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


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.