Faster Approximate Lossy Generalized Flow via Interior Point Algorithms
This work provides faster algorithms for generalized flow problems, which are important in network optimization, but the improvement is incremental over existing methods.
The authors present faster approximation algorithms for lossy generalized network flow, achieving an additive epsilon approximation in tildeO(m^(3/2) * log(1/epsilon)) time, improving over previous algorithms by a factor of approximately m^(1/2).
We present faster approximation algorithms for generalized network flow problems. A generalized flow is one in which the flow out of an edge differs from the flow into the edge by a constant factor. We limit ourselves to the lossy case, when these factors are at most 1. Our algorithm uses a standard interior-point algorithm to solve a linear program formulation of the network flow problem. The system of linear equations that arises at each step of the interior-point algorithm takes the form of a symmetric M-matrix. We present an algorithm for solving such systems in nearly linear time. The algorithm relies on the Spielman-Teng nearly linear time algorithm for solving linear systems in diagonally-dominant matrices. For a graph with m edges, our algorithm obtains an additive epsilon approximation of the maximum generalized flow and minimum cost generalized flow in time tildeO(m^(3/2) * log(1/epsilon)). In many parameter ranges, this improves over previous algorithms by a factor of approximately m^(1/2). We also obtain a similar improvement for exactly solving the standard min-cost flow problem.