Answers are grounded in this paper and cite their sources.
In this work, we study the parallel complexity of the Euclidean minimum-weight perfect matching (EWPM) problem. Here our graph is the complete bipartite graph G on two sets of points A and B in R² and the weight of each edge is the Euclidean distance between the corresponding points. The weighted perfect matching problem on general bipartite graphs is known to be in RNC [Mulmuley, Vazirani, and Vazirani, 1987], and Quasi-NC [Fenner, Gurjar, and Thierauf, 2016]. Both of these results work only when the weights are of O(log n) bits. It is a long-standing open question to show the problem to be in NC. First, we show that for EWPM, a linear number of bits of approximation is required to distinguish between the minimum-weight perfect matching and other perfect matchings. Next, we show that the EWPM problem that allows up to 1/poly(n) additive error, is in NC.
No takes yet. Share an insight, caveat, or question.
Bhore et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: