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)$.