A polylogarithmic approximation of the minimum bisection

A bisection of a graph with n vertices is a partition of its vertices into two sets, each of size n/2. The bisection cost is the number of edges connecting the two sets. Finding the bisection of minimum cost is NP-hard. We present an algorithm that finds a bisection whose cost is within ratio of O(log/sup 2/ n) from the optimal. For graphs excluding any fixed graph as a minor (e. g. planar graphs) we obtain an improved approximation ratio of O(log n). The previously known approximation ratio for bisection was roughly /spl radic/n.

Authors

• Uriel Feige
• Robert Krauthgamer

Keywords

• Cost function
• Joining processes
• Polynomials
• Computer science
• Mathematics
• Partitioning algorithms
• Minimization methods
• Approximation algorithms
• Particle separators
• Dynamic programming
• Bisection
• Loss Of Generality
• Root Node
• Nondecreasing
• Leaf Node
• Vertices
• Stages Of Decomposition
• Joining Tree
• Table Entries
• Input Graph
• Minimum Charge
• Left Child
• Sum Of Charges
• Polylogarithmic
• Approximate Ratio
• Planar Graphs
• Upper Bound
• Quadratic Function
• Tree Nodes
• Root Of The Tree
• Divide-and-conquer
• Empty Set
• Binary Tree
• Binary Search
• Relation Graph
• Part Of The Graph
• Label Consistency
• Optimal Cut
• Divide-and-conquer Approach
• Family Of Graphs