Let be a network for an assignment problem with 2n nodes and m edges, in which the largest edge cost is C. Recently the class of instances of bipartite matching problems has been shown to be in RNC provided that C is for some fixed k. The authors show how to use scaling so as to develop an improved parallel algorithm and show that bipartite matching problems are in the class RNC provided that C=O for some fixed k. They then generalize these results to minimum-cost flow problems. Let U be an upper bound on the capacities of the edges and on the largest demand. The authors show that the minimum-cost flow problems is in the class RNC, provided that log for some fixed k. Thus the minimum-cost flow problem is in the class RNC even when the magnitude of the costs and capacities are allowed to grow faster than any polynomial in n. The key to the present approach is to reduce the number of processors needed from an amount that is proportional to the magnitude of the largest edge cost to an amount that is independent of the magnitude of the largest edge cost. The tradeoff is an increase in the running time that grows linearly in .
