Balanced Graph Partitioning Export

@article{citeulike:1003853, abstract = {Abstract\ \ We consider the problem of partitioning a graph into k components of roughly equal size while minimizing the capacity of the edges between different components of the cut. In particular we require that for a parameter ν ≥ 1, no component contains more than ν n/k of the graph vertices. For k = 2 and ν = 1 this problem is equivalent to the well-known Minimum Bisection problem for which an approximation algorithm with a polylogarithmic approximation guarantee has been presented in [FK]. For arbitrary k and ν ≥ 2 a bicriteria approximation ratio of O(log n) was obtained by Even et al. [ENRS1] using the spreading metrics technique. We present a bicriteria approximation algorithm that for any constant ν \> 1 runs in polynomial time and guarantees an approximation ratio of O(log1.5n) (for a precise statement of the main result see Theorem 6). For ν = 1 and k ≥ 3 we show that no polynomial time approximation algorithm can guarantee a finite approximation ratio unless P = NP.}, author = {Andreev, Konstantin and R\"{a}cke, Harald}, booktitle = {Theory of Computing Systems}, citeulike-article-id = {1003853}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1204515.1204522}, citeulike-linkout-1 = {http://dx.doi.org/10.1007/s00224-006-1350-7}, citeulike-linkout-2 = {http://www.ingentaconnect.com/content/klu/224/2006/00000039/00000006/00001350}, citeulike-linkout-3 = {http://www.springerlink.com/content/d752rl3r2r765846}, day = {5}, doi = {10.1007/s00224-006-1350-7}, issn = {1432-4350}, journal = {Theory of Computing Systems}, keywords = {partitions}, month = {November}, number = {6}, pages = {929--939}, posted-at = {2008-09-19 14:59:12}, priority = {2}, publisher = {Springer}, title = {Balanced Graph Partitioning}, url = {http://dx.doi.org/10.1007/s00224-006-1350-7}, volume = {39}, year = {2006} }

TY - JOUR ID - citeulike:1003853 L3 - citeulike-article-id:1003853 N2 - Abstract  We consider the problem of partitioning a graph into k components of roughly equal size while minimizing the capacity of the edges between different components of the cut. In particular we require that for a parameter ν ≥ 1, no component contains more than ν n/k of the graph vertices. For k = 2 and ν = 1 this problem is equivalent to the well-known Minimum Bisection problem for which an approximation algorithm with a polylogarithmic approximation guarantee has been presented in [FK]. For arbitrary k and ν ≥ 2 a bicriteria approximation ratio of O(log n) was obtained by Even et al. [ENRS1] using the spreading metrics technique. We present a bicriteria approximation algorithm that for any constant ν > 1 runs in polynomial time and guarantees an approximation ratio of O(log1.5n) (for a precise statement of the main result see Theorem 6). For ν = 1 and k ≥ 3 we show that no polynomial time approximation algorithm can guarantee a finite approximation ratio unless P = NP. IS - 6 JF - Theory of Computing Systems SN - 1432-4350 EP - 939 TI - Balanced Graph Partitioning PB - Springer VL - 39 T2 - Theory of Computing Systems SP - 929 KW - partitions AU - Andreev, Konstantin AU - Räcke, Harald PY - 2006/11/05/ UR - http://dx.doi.org/10.1007/s00224-006-1350-7 ER -