Geodesic
Minimum nonuniform graph partitioning with unrelated weights
Sbornik. Mathematics, Tome 208 (2017) no. 12, pp. 1835-1853 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We give a bi-criteria approximation algorithm for the Minimum Nonuniform Graph Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz and Talwar. In this problem, we are given a graph $G=(V,E)$ and $k$ numbers $\rho_1,\dots, \rho_k$. The goal is to partition $V$ into $k$ disjoint sets (bins) $P_1,\dots, P_k$ satisfying $|P_i|\leq \rho_i |V|$ for all $i$, so as to minimize the number of edges cut by the partition. Our bi-criteria algorithm gives an $O(\sqrt{\log |V| \log k})$ approximation for the objective function in general graphs and an $O(1)$ approximation in graphs excluding a fixed minor. The approximate solution satisfies the relaxed capacity constraints $|P_i| \leq (5+ \varepsilon)\rho_i |V|$. This algorithm is an improvement upon the $O(\log |V|)$-approximation algorithm by Krauthgamer, Naor, Schwartz and Talwar. We extend our results to the case of ‘unrelated weights’ and to the case of `unrelated $d$-dimensional weights'. A preliminary version of this work was presented at the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014). Bibliography: 7 titles.
Keywords: minimum nonuniform graph partitioning problem, minimum nonuniform graph partitioning problem with unrelated weights, approximation for trees, approximation algorithm, semidefinite programming. 
@article{SM_2017_208_12_a5,
     author = {K. S. Makarychev and Yu. S. Makarychev},
     title = {Minimum nonuniform graph partitioning with unrelated weights},
     journal = {Sbornik. Mathematics},
     pages = {1835--1853},
     year = {2017},
     volume = {208},
     number = {12},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2017_208_12_a5/}
}
TY  - JOUR
AU  - K. S. Makarychev
AU  - Yu. S. Makarychev
TI  - Minimum nonuniform graph partitioning with unrelated weights
JO  - Sbornik. Mathematics
PY  - 2017
SP  - 1835
EP  - 1853
VL  - 208
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/SM_2017_208_12_a5/
LA  - en
ID  - SM_2017_208_12_a5
ER  - 
%0 Journal Article
%A K. S. Makarychev
%A Yu. S. Makarychev
%T Minimum nonuniform graph partitioning with unrelated weights
%J Sbornik. Mathematics
%D 2017
%P 1835-1853
%V 208
%N 12
%U http://geodesic.mathdoc.fr/item/SM_2017_208_12_a5/
%G en
%F SM_2017_208_12_a5
K. S. Makarychev; Yu. S. Makarychev. Minimum nonuniform graph partitioning with unrelated weights. Sbornik. Mathematics, Tome 208 (2017) no. 12, pp. 1835-1853. http://geodesic.mathdoc.fr/item/SM_2017_208_12_a5/

[1] A. Amir, J. Ficler, R. Krauthgamer, L. Roditty, O. Sar Shalom, “Multiply balanced $k$-partitioning”, LATIN2014: theoretical informatics, Lecture Notes in Comput. Sci., 8392, Springer, Heidelberg, 2014, 586–597 | DOI | MR | Zbl

[2] N. Bansal, U. Feige, R. Krauthgamer, K. Makarychev, V. Nagarajan, J. Naor, R. Schwartz, “Min-max graph partitioning and small set expansion”, SIAM J. Comput., 43:2 (2014), 872–904 | DOI | MR | Zbl

[3] E. Chlamtac, K. Makarychev, Y. Makarychev, “How to play unique games using embeddings”, FOCS' 06 Proceedings of the 47th annual IEEE symposium on foundations of computer science (Berkeley, CA), IEEE Computer Soc., Washington, DC, 2006, 687–696 | DOI

[4] R. Krauthgamer, J. Naor, R. Schwartz, “Partitioning graphs into balanced components”, SODA' 09 Proceedings of the 20th annual ACM–SIAM symposium on discrete algorithms (New York, NY, 2009), SIAM, Philadelphia, PA, 2009, 942–949 | DOI | MR

[5] R. Krauthgamer, J. Naor, R. Schwartz, K. Talwar, “Non-uniform graph partitioning”, SODA' 14 Proceedings of the 25th annual ACM–SIAM symposium on discrete algorithms (Portland, OR, 2014), ACM, New York, 2014, 1229–1243 | DOI | MR

[6] A. Louis, K. Makarychev, “Approximation algorithm for sparsest $k$-partitioning”, SODA' 14 Proceedings of the 25th annual ACM–SIAM symposium on discrete algorithms (Portland, OR, 2014), ACM, New York, 2014, 1244–1255 | DOI | MR

[7] H. Räcke, “Optimal hierarchical decompositions for congestion minimization in networks”, STOC' 08 Proceedings of the 40th annual ACM symposium on theory of computing, ACM, New York, 2008, 255–263 | DOI | MR | Zbl