Approximation through Multicommodity Flow

The first approximate max-flow-min-cut theorem for general multicommodity flow is proved. It is used to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF identical to formula, via minimization problems, and other problems. Also presented are approximation algorithms for chordalization of a graph and for register sufficiency that are based on undirected and directed node separators. >

Authors

• Philip N. Klein
• Ajit Agrawal
• R. Ravi 0001
• Satish Rao

Keywords

• Approximation algorithms
• Upper bound
• Minimization methods
• Particle separators
• Laboratories
• Polynomials
• Multi-commodity Flow
• Undirected
• Estimation Algorithm
• Minimization Problem
• Linear System
• Proof Of Theorem
• Positive Definite Matrix
• Directed Graph
• Flow Problem
• Small Cost
• Polynomial-time Algorithm
• Nonzero Entries
• Capacity Utilization
• Joining Tree
• Input Graph
• Performance Guarantees
• Algorithm In Section
• NP-complete Problem
• Minimum Cut
• Incident Edges
• Gaussian Elimination
• Sum Capacity
• Concurrent Problems
• Symmetric System
• Capacity Ratio
• Shortest Path
• System Of Equations
• Root Of The Tree
• Subtree
• System Of Linear Equations
• Topological States
• Optimal Order
• Minimum Height
• Proof Sketch
• Graph Optimization
• Polylogarithmic