I am looking for a simple to implement algorithm for the bipartite euclidean matching problem (or an implementation of any practical algorithm). I am aware of Agarwal's paper, but I would like to implement something simpler. The simplest idea I could come up with was starting with some initial matching (possibly random) and then minimizing the energy through simulated annealing. In my case the vertices of each class are ~ $2^{14} - 2^{20}$ so brute-forcing the solution is not realistic. A benefit of the stochastic method is that I also do not necessarily need to compute the possibly $2^{20} \times 2^{20}$ distance matrix, since I can compute the distances for each swap on demand. Any suggestions/alternatives are welcome.

  • $\begingroup$ Just a confirmation: I might have come with the same approach. A former colleague of mine used Metropolis Monte Carlo for minimizing the electrostatic energy of point charges, so this could work here as well. You will likely have to fiddle around a lot with the steps (how many swaps in one step, which connections to exchange, e.g. only nearest neighbours, and so on). Moreover, I wouldn't start randomly, but using a greedy matching, e.g. by cycling over all particles and choose the nearest available partner. It would be nice to let us know how it worked (through an answer to your own question). $\endgroup$ – davidhigh 5 hours ago
  • $\begingroup$ @davidhigh Thanks for the suggestion. I had not thought about using Metropolis Monte Carlo. Linking the nearest points will definitely provide a nice initialization for methods that are able to use the initialization to their advantage. On the other hand it will likely break greedier methods since it may be a hard to escape local minimum. $\endgroup$ – lightxbulb 5 hours ago

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.