TY - GEN

T1 - Nonuniform graph partitioning with unrelated weights

AU - Makarychev, Konstantin

AU - Makarychev, Yury

PY - 2014

Y1 - 2014

N2 - We give a 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 ρ1,..., ρk. The goal is to partition the graph into k disjoint sets P1,..., Pk satisfying |Pi| ≤ ρin so as to minimize the number of edges cut by the partition. Our algorithm has an approximation ratio of O(√log n log k)for general graphs, and an O(1) approximation for graphs with excluded minors. This is an improvement upon the O(logn) 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 case of "unrelated weights" and to the case of "unrelated d-dimensional weights". In the former case, different vertices may have different weights and the weight of a vertex may depend on the set Pi the vertex is assigned to. In the latter case, each vertex u has a d-dimensional weight r(u,i) = (r1(u,i),..., rd (u,i)) if u is assigned to Pi. Each set Pi has a d-dimensional capacity c(i) = (c1(i),..., cd (i)). The goal is to find a partition such that ∑u∈Pi r(u, i) ≤ c(i) coordinate-wise.

AB - We give a 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 ρ1,..., ρk. The goal is to partition the graph into k disjoint sets P1,..., Pk satisfying |Pi| ≤ ρin so as to minimize the number of edges cut by the partition. Our algorithm has an approximation ratio of O(√log n log k)for general graphs, and an O(1) approximation for graphs with excluded minors. This is an improvement upon the O(logn) 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 case of "unrelated weights" and to the case of "unrelated d-dimensional weights". In the former case, different vertices may have different weights and the weight of a vertex may depend on the set Pi the vertex is assigned to. In the latter case, each vertex u has a d-dimensional weight r(u,i) = (r1(u,i),..., rd (u,i)) if u is assigned to Pi. Each set Pi has a d-dimensional capacity c(i) = (c1(i),..., cd (i)). The goal is to find a partition such that ∑u∈Pi r(u, i) ≤ c(i) coordinate-wise.

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

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

U2 - 10.1007/978-3-662-43948-7_67

DO - 10.1007/978-3-662-43948-7_67

M3 - Conference contribution

AN - SCOPUS:84904208123

SN - 9783662439470

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 812

EP - 822

BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings

PB - Springer Verlag

T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014

Y2 - 8 July 2014 through 11 July 2014

ER -