ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsGraph TheoryNetwork Flow AlgorithmsApproximation Algorithms For Network FlowsComputational Complexity Of Graph AlgorithmsMaximum FlowMaximum Flow AlgorithmsMaximum Flow ProblemsNetwork Flow ProblemsPlanar Graphs
We establish several approximate max-integral-flow / min-multicut theorems. While in general this ratio can be very large, we prove strong approximation ratios in the case where the min-multicut is a constant fraction ε of the total capacity of the graph. This setting is motivated by several combinatorial and algorithmic applications. Prior to this work, a general max-integral-flow / min-multicut bound was known only for the special case where the graph is a tree. We prove that, for arbitrary graphs, the max-integral-flow / min-multicut ratio is O(ε-1 log k), where k is the number of commodites; for graphs excluding a fixed subgraph as a minor (for instance, planar graphs), O(1 / ε); and, for dense graphs, O(1√ε). Our proofs are constructive in the sense that we give efficient algorithms which compute either an integral flow achieving the claimed approximation ratios, or a witness that the precondition is violated.
18
Maximal Flow Through a Network
L. R. Ford, D. R. Fulkerson · Canadian Journal of Mathematics · 1956 · 2.3K citations · Full text
Property testing and its connection to learning and approximation
Oded Goldreich, Shari Goldwasser, Dana Ron · Journal of the ACM · 1998 · 1.1K citations · Full text
The geometry of graphs and some of its algorithmic applications
Nathan Linial, Eran London, Yuri Rabinovich · COMBINATORICA · 1995 · 974 citations
The Complexity of Multiterminal Cuts
Elias Dahlhaus, D. S. Johnson, Christos H. Papadimitriou et al. · SIAM Journal on Computing · 1994 · 666 citations