We present asymptotically faster approximation algorithms for the generalized flow problems in which multipliers on edges are at most 1. For this lossy version of the maximum generalized flow problem, we obtain an additive approximation of the maximum flow in time e O " m 3/2 log(U/ ) 2 " , where m is the number of edges in the graph, all capacities are integers in the range {1, . . . , U }, and all loss multipliers are ratios of integers in this range. For minimum cost lossy generalized flow with costs in the range {1, . . . , U }, we obtain a flow that has value within an additive of the maximum value and cost at most the optimal cost. In many parameter ranges, these algorithms improve over the previously fastest algorithms for the generalized maximum flow problem by a factor of m 1/2 and for the minimum cost generalized flow problem by a factor of approximately m 1/2 / 2 . The algorithms work by accelerating traditional interior point algorithms by quickly solving the system of linear equations that arises in each step. The contributions of this paper are twofold. First, we analyze the performance of interior point algorithms with approximate linear system solvers. This analysis alone provides an algorithm for the standard minimum cost flow problem that runs in time " over previous algorithms. Second, we examine the linear equations that arise when using an interior point algorithm to solve generalized flow problems. We observe that these belong to the family of symmetric M -matrices, and we then develop e O (m)-time al- * This material is based upon work supported by the National Science Foundation under Grant Nos. CCF-0707522 and CCF-0634957. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. gorithms for solving linear systems in these matrices. These algorithms reduce the problem of solving a linear system in a symmetric M -matrix to that of solving O (log n) linear systems in symmetric diagonally-dominant matrices, which we can do in time e O (m) using the algorithm of Spielman and Teng. All of our algorithms operate on numbers of bit length at most O (log nU/ ).
To the best of our knowledge this connection was first observed in REF , leading to, among others, a faster algorithm for minimum cost flow.
Faster approximate lossy generalized flow via interior point algorithms
STOC '08
Mathematics Computer Science