8
$\begingroup$

As is well known, assignment problems for $n$-partite graphs, with $n$>2 are NP-hard, where as assignment problems on bipartite graphs can be solved in polynomial time using the Kuhn's Hungarian algorithm.

There is a 1992 paper by Crama & Spieksma (link to paper) that discusses two special case of 3AP:

  1. 3AP where the cost is the sum of the costs within the triple (i.e. circumference of the triangle)

  2. 3AP where the cost is the sum of the two shortest lengths

Both are shown to still be NP hard, but the do give a heuristic, the solution of which is at most 3/2 or 4/3 of the correct solution respectively.

There is an interesting recent review paper (link to paper) by Gutin and Karapetyan discussing various heuristics for n-AP and their performance in general ,

What is the best-performing heuristic to solve class 1 of Crama & Spieksma. Is it their original heuristic as given in their paper or have there been new developments? Bonus points if it is broken down to Hungarian Algorithm for example as in Huang & Lim (PDF)

Improve this question
$\endgroup$

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.