Suppose I have an assignment problem with $n$ workers and $n$ jobs and its optimal solution.

Now another worker and another job comes along and we are given all new costs. Is there an efficient method for finding the new optimal solution given the old one? I'm looking for an algorithm with lower complexity than recalculating everything, i.e. better than $O(n^3)$.

Thanks ;)

  • $\begingroup$ What exactly do you mean by 'all new costs'? Do you mean that also the cost of an assignment of one of the first $n$ workers to one of the first $n$ jobs has a new cost which is not related to the previous cost? In this case, I am afraid, you will have to recalculate everything. $\endgroup$ – philipph Sep 17 '14 at 16:16
  • $\begingroup$ @philipph No, sorry. Maybe that wasn't clear. The old costs stay the same. I just meant that we now know the costs linked to the new worker or to the new job. $\endgroup$ – Alex Sep 17 '14 at 17:06

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.