Computer Science – Data Structures and Algorithms
Scientific paper
2008-03-06
Computer Science
Data Structures and Algorithms
v2: bug fixes and some expanded proofs
Scientific paper
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.
Daitch Samuel I.
Spielman Daniel A.
No associations
LandOfFree
Faster Approximate Lossy Generalized Flow via Interior Point Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Faster Approximate Lossy Generalized Flow via Interior Point Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Approximate Lossy Generalized Flow via Interior Point Algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-251998