2008/03/06 by Samuel I. Daitch, Daniel A. Spielman, Daitch, Samuel I. +1 · 8 citations
Computer Science · Engineering · Physics and Astronomy · #Advanced Numerical Methods in Computational Mathematics #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Model Reduction and Neural Networks #Numerical Analysis (math.NA) #Numerical Methods and Algorithms
paper · pdf · doi:10.48550/arxiv.0803.0988
openalex publication_date 2008/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.