Ahuja R: New scaling algorithms for the assignment and minimummean cycle problems.Math Program

In this paper, we suggest new scaling algorithms for the assignment and minimum cycle mean problems. Our assignment algorithm is based on applying scaling to a hybrid version of the recent auction algorithm of Bertsekas and the sequential shortest path algorithm. The algorithm proceeds by relaxing the optimality conditions and the amount of relaxation is successively reduced to zero. On a network with 2n nodes, m arcs, and integer arc costs bounded by C, the algorithm runs in O(--n m log nC) time and uses simple data structures. This time bound is comparable to the time taken by Gabow and Tarjan's scaling algorithm and is better than all other time bounds under the similarity assumption, i.e., C = O(nk) for some k. We next consider the minimum cycle mean problem. The mean cost of a cycle is defined as the cost of the cycle divided by the number of arcs it contains. The minimum cycle mean problem is to identify a cycle whose mean cost is minimum. We show that by using ideas of the assignment algorithm in an approximate binary search procedure, the minimum mean cycle problem can also b