Say you have a graph consisting of $k$ red nodes and $k$ blue nodes in Euclidean $2$-d space. There is an edge between every red-blue pair, and edge weights are distances. Our goal is to find the min-weight matching.

The Hungarian algorithm solves the more general case where the edge weights are arbitrary. Is there a more efficient approach that takes advantage of the Euclidean aspect?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.