Combinatorial interior point methods for generalized network flow problems (Q1396212)

The paper is concerned with generalized minimum cost flow problems. Compared with a pure network flow problem, in generalized network flow problems each arc has a gain/loss factor associated with it. Since the pure and generalized problems are linear programs, any linear programming algorithms, in particular, interior point methods can be used to solve these problems. However if interior point methods are applied directly, they are not combinatorial. The authors present combinatorial interior point methods for the generalized minimum cost flow problems and the generalized circulation problems. The algorithms run in \(O(m^2 n^2 (\log m+\log^2 n)L)\) time, where \(m\) and \(n\) are the number of arcs and nodes in the graph, and \(L\) is the length of the input data.