A NEW METHOD FOR THE LINEAR ASSIGNMENT PROBLEM

Suppose we are given a feasible solution for a linear assignment problem (AP). Is this solution an optimal solution for the given AP? In this paper we prove necessary and sufficient conditions of optimality for an AP solution. Then we present a new method for solving the AP. The method starts with a feasible solution and if possible improves it then tests its optimality. If optimality of the current solution cannot be confirmed it uses the Hungarian method to identify an optimal solution. The computational testing on those problems that we have solved without the need to use the Hungarian method in the form of operations counts instead of CPU time so that the results are largely independent of the computing environment supports (but does not prove) the hypothesis that the method runs in expected time 0(n**3) on the worst case problems. This is better than the Hungarian method that runs in O(n**4 ) time and is comparable with Lawler's implementation, a successive shortest path algorithm, of the Hungarian method with the complexity of O(n**3 ). One very important application of this method is in the traveling salesman problem (TSP) tour improvements.