Nonuniform Graph Partitioning with Unrelated Weights
Authors:
Preprint
Abstract
We give a simple bi-criteria approximation algorithm for the Minimum Nonuniform Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz and Talwar (2014). In this problem, we are given a graph $G=(V,E)$ on $n$ vertices and $k$ numbers $\rho_1,\dots, \rho_k$. The goal is to partition the graph into $k$ disjoint sets $P_1,\dots, P_k$ satisfying $|P_i|\leq \rho_i n$ so as to minimize the number of edges cut by the partition. Our algorithm has an approximation ratio of $O(\sqrt{\log n \log k})$ for general graphs, and an $O(1)$ approximation for graphs with excluded minors. This is an improvement upon the $O(\log n)$ algorithm of Krauthgamer, Naor, Schwartz and Talwar (2014). Our approximation ratio matches the best known ratio for the Minimum (Uniform) $k$-Partitioning problem. We extend our results to the "unrelated" case when different vertices may have different weights and the weight of a vertex may depend on the set $P_i$ the vertex is assigned to.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Min-Max Graph Partitioning and Small Set ExpansionSIAM Journal on Computing, 2014
- Non-Uniform Graph Partitioning2013
- Approximation Algorithm for Sparsest k-Partitioning2013
- Partitioning Graphs into Balanced Components2009
- Optimal hierarchical decompositions for congestion minimization in networks2008
- How to Play Unique Games Using Embeddings2006