2
$\begingroup$

I am looking for a fast solution to the assignment problem for large cost matrices (5000x5000 or larger). The Hungarian algorithm is $O^3$, which is impractical for any moderately large problem. Are there similar algorithms but sub-optimal and fast, possibly in R (or Python)?

The problem I'm working consists of finding the best pairs of points in sets A and B (|A|=|B|), minimizing their overall distance.

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you sure the Hungarian algorithm is infeasible? Have you tried it? $5000^3$ operations sounds like the kind of thing that a computer might be able to do in a few minutes or hours. I'd also suggest you try an off-the-shelf linear programming solver; try searching Google Scholar for parallel algorithms for the assignment problem; and try looking into the auction algorithm, which Wikipedia's article on the assignment problem claims can be used to solve the assignment problem. Then you might edit your question to summarize what you've found. $\endgroup$ – D.W.♦ Feb 23 '19 at 22:15
  • $\begingroup$ Some linear programming solvers can stop early with a sub-optimal solution. The Hungarian algorithm can also be stopped early, with a sub-optimal solution. I'd suggest trying those as well to see if you're satisfied with them. $\endgroup$ – D.W.♦ Feb 23 '19 at 22:18
  • $\begingroup$ I tried the Hungarian algorithm and it wasn't done after 24 hours. As I don't need optimal solutions and I need to calculate this frequently, I am aiming at something solvable in 10-15 min on an ordinary PC. $\endgroup$ – Strabonio Feb 23 '19 at 22:42
  • $\begingroup$ @Strabonio What is the range of cost? The reason I am asking is to check whether a layered approach may boost performance a lot or not. $\endgroup$ – John L. Feb 25 '19 at 2:44

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.