5
$\begingroup$

Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or variants.

However, if $n$ is large, $O(n^3)$ may not be feasible from a timing perspective. Moreover, storing the complete $n^2$ cost matrix may require a prohibitive amount of memory.

Are there heuristic algorithms that give "good enough" solutions, with are significantly faster? I have seen some algorithms that claim to be faster, but they assume the number of edges is smaller than $O(n^2)$, which is not true in the dense case.

$\endgroup$
5
$\begingroup$

This paper has a painfully detailed table on what you can achieve using (currently known) deterministic, randomized and $\epsilon$-approximation algorithms. To summarize, for the bipartite case (all assuming integer weights bounded by $N$):

  1. Deterministic time $O(n^2 \sqrt n \log N)$.
  2. Randomized $O(n^{2.373} N)$.
  3. $(1 - \epsilon)$-approximation in $O(n^2 \epsilon^{-1} \log N)$.

These algorithms are mostly very complex and go through $LP$ formulations. It is unlikely that any of them are truly what you're looking for. Also, regarding their use of space, I am not sure, but you can follow the papers for the different algorithms and see for yourself, if you can make them work in less space. (By the way, isn't your cost function already using quadratic space?)

If you want a heuristic with no provable guarantees, then I recommend the simple local search. You basically start with some random permutation (this is a feasible assignment, since your bipartite graph is complete) and make random swaps that improve the cost. If you do many such searches, you get a good solution more often then not. You can make the whole thing run in $O(t (n + s))$ time and linear space, if you do $t$ searches (from random permutations), each for $s$ steps. Choose $t, s$ to trade-off quality of the solution with complexity.

$\endgroup$
  • $\begingroup$ Thank you! My TD;LR take from this is that, no, there isn't really a (significantly) more efficient method, especially as I assume that the 2.373 factor (matrix mult.) is actually 3 in most practical cases. Sometimes knowing that a solution doesn't exist is just as helpful. $\endgroup$ – nbubis Nov 5 '16 at 19:47
  • $\begingroup$ @nbubis some things you may want to consider: (1) there might be newer results that I am missing, the paper was published in 2014. (2) local search is a very generic heuristic, I think it will work well in this case, but there might be other answers with heuristics specifically tailored to this problem. (3) if there is some extra structure on your cost function, knowing that might help break the bounds above, for example is it metric? $\endgroup$ – aelguindy Nov 5 '16 at 19:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.