Non-uniform graph partitioning

摘要: We consider the problem of Non-Uniform Graph Partitioning, where input is an edge-weighted undirected graph G = (V, E) and k capacities n1, ..., nk, goal to find a partition {S1, S2, Sk} V satisfying |Sj| ≤ nj for all 1 j k, that minimizes total weight edges crossing between different parts. This natural partitioning arises in practical scenarios, generalizes well-studied balanced problems such as Minimum Bisection, Balanced Cut, k-Partitioning. Unlike these problems, Partitioning seems be resistant many known techniques, spreading metrics, recursive partitioning, Racke's tree decomposition, because can function n could magnitudes.We present bicriteria approximation algorithm approximates objective within O(log n) factor while deviating from required by at most constant factor. Our approach apply stopping-time based concentration results simple randomized rounding configuration LP. These bounds are needed commonly used techniques bounded differences conditioned variances do not suffice.