Sparsest Cut
- PDF / 231,914 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 88 Downloads / 161 Views
S
Sparsest Cut
12. Woodruff, D.: Lower Bounds for Additive Spanners, Emulators, and More. In: Proc. of Symp. on Foundations of Computer Science, Berckeley, Oct. 2006, pp. 389–398
Key Results
Sparsest Cut 2004; Arora, Rao, Vazirani SHUCHI CHAWLA Department of Computer Science, University of Wisconsin–Madison, Madison, WI, USA Keywords and Synonyms Minimum ratio cut Problem Definition In the Sparsest Cut problem, informally, the goal is to partition a given graph into two or more large pieces while removing as few edges as possible. Graph partitioning problems such as this one occupy a central place in the theory of network flow, geometric embeddings, and Markov chains, and form a crucial component of divide-and-conquer approaches in applications such as packet routing, VLSI layout, and clustering. Formally, given a graph G = (V ; E), the sparsity or edge expansion of a non-empty set S V, jSj 12 jVj, is defined as follows: jE(S; V n S)j ˛(S) = : jSj The sparsity of the graph, ˛(G), is then defined as follows: ˛(G) =
min
S V ;jSj 12 jV j
at least cjVj vertices. The goal in the Balanced Separator problem is to find a c-balanced partition with the minimum sparsity. This sparsity is denoted ˛c (G).
˛(S) :
The goal in the Sparsest Cut problem is to find a subset S V with the minimum sparsity, and to determine the sparsity of the graph. The first approximation algorithm for the Sparsest Cut problem was developed by Leighton and Rao in 1988 [13]. Employing a linear programming relaxation of the problem, they obtained an O(log n) approximation, where n is the size of the input graph. Subsequently Arora, Rao and Vazirani [4] obtained an improvement over Leighton and Rao’s algorithm using a semi-definite programming prelaxation, approximating the problem to within an O( log n) factor. In addition to the Sparsest Cut problem, Arora et al. also consider the closely related Balanced Separator problem. A partition (S; V n S) of the graph G is called a cbalanced separator for 0 < c 12 , if both S and V n S have
p Arora et al. provide an O( log n) pseudo-approximation to the balanced-separator problem using semi-definite programming. In particular, given a constant c 2 (0; 12 ], they produce a separator with balance c 0 that is slightly 0 worse p than c (that is, c < c), but sparsity within an O( log n) factor of the sparsity of the optimal c-balanced separator. Theorem 1 Given a graph G = (V; E), let ˛c (G) be the minimum edge expansion of a c-balanced separator in this graph. Then for every fixed constant a < 1, there exists a polynomial-time algorithm for finding a c 0 -balanced sep0 arator p in G, with c ac, that has edge expansion at most O( log n˛c (G)). Extending this theorem to include unbalanced partitions, Arora et al. obtain the following: Theorem 2 Let G = (V; E) be a graph with sparsity ˛(G). Then there exists a polynomial-time algorithm for finding a partitionp (S; V n S), with S V, S ¤ ;, having sparsity at most O( log n˛(G)). An important contribution of Arora et al. is a new geometric characterization of
Data Loading...
