Key points are not available for this paper at this time.
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 (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 1poly (n) additive error, is in NC.
Bhore et al. (Wed,) studied this question.