TY - GEN

T1 - Min-max graph partitioning and small set expansion

AU - Bansal, Nikhil

AU - Feige, Uriel

AU - Krauthgamer, Robert

AU - Makarychev, Konstantin

AU - Nagarajan, Viswanath

AU - Naor, Joseph

AU - Schwartz, Roy

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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: (i) the k parts need to be of equal size, and (ii) the parts must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an O(√log n log k)-approximation algorithm. This improves over an O(log 2 n) approximation for the second version due to Svitkina and Tardos, 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 ⊆ V of size |S| ≤ ρn with minimum edge-expansion. We give an O(√log n log (1/ρ)) bicriteria approximation algorithm for the general case of Small Set Expansion and O(1) approximation algorithm for graphs that exclude any fixed minor.

AB - 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: (i) the k parts need to be of equal size, and (ii) the parts must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an O(√log n log k)-approximation algorithm. This improves over an O(log 2 n) approximation for the second version due to Svitkina and Tardos, 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 ⊆ V of size |S| ≤ ρn with minimum edge-expansion. We give an O(√log n log (1/ρ)) bicriteria approximation algorithm for the general case of Small Set Expansion and O(1) approximation algorithm for graphs that exclude any fixed minor.

UR - http://www.scopus.com/inward/record.url?scp=84862591202&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862591202&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2011.79

DO - 10.1109/FOCS.2011.79

M3 - Conference contribution

AN - SCOPUS:84862591202

SN - 9780769545714

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 17

EP - 26

BT - Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

Y2 - 22 October 2011 through 25 October 2011

ER -