Computer Science – Data Structures and Algorithms
Scientific paper
2011-10-19
Computer Science
Data Structures and Algorithms
Full version of paper appearing in FOCS 2011, 29 pages
Scientific paper
We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the k parts need to be of equal-size, and where they must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an $O(\sqrt{\log n\log k})$-approximation algorithm. This improves over an $O(\log^2 n)$ approximation for the second version, and roughly $O(k\log n)$ approximation for the first version that follows from other previous work. We also give an improved O(1)-approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the Small-Set Expansion problem. In this problem, we are given a graph G and the goal is to find a non-empty set $S\subseteq V$ of size $|S| \leq \rho n$ with minimum edge-expansion. We give an $O(\sqrt{\log{n}\log{(1/\rho)}})$ bicriteria approximation algorithm for the general case of Small-Set Expansion, and O(1) approximation algorithm for graphs that exclude any fixed minor.
Bansal Nikhil
Feige Uriel
Joseph
Krauthgamer Robert
Makarychev Konstantin
No associations
LandOfFree
Min-Max Graph Partitioning and Small Set Expansion 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 Min-Max Graph Partitioning and Small Set Expansion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Min-Max Graph Partitioning and Small Set Expansion will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-597540