DocumentCode
2734051
Title
A polylogarithmic approximation of the minimum bisection
Author
Feige, Uriel ; Krauthgamer, Robert
Author_Institution
Dept. of Comput. Sci. & Appl. Math., Weizmann Inst. of Sci., Rehovot, Israel
fYear
2000
fDate
2000
Firstpage
105
Lastpage
115
Abstract
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(log2 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 √n
Keywords
computational complexity; computational geometry; graph theory; approximation ratio; bisection cost; complexity; edges; graph; minimum bisection; polylogarithmic approximation; vertex partitioning; vertices; Approximation algorithms; Computer science; Cost function; Dynamic programming; Joining processes; Mathematics; Minimization methods; Particle separators; Partitioning algorithms; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on
Conference_Location
Redondo Beach, CA
ISSN
0272-5428
Print_ISBN
0-7695-0850-2
Type
conf
DOI
10.1109/SFCS.2000.892070
Filename
892070
Link To Document