Approximation Algorithms for Hypergraph Small-Set Expansion and Small-Set Vertex Expansion

by Anand Louis and Yury Makarychev

Theory of Computing, Volume 12(17), pp. 1-25, 2016

Bibliography with links to cited articles

[1]   Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev: O(√ ----
  logn) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems. In Proc. 37th STOC, pp. 573–581. ACM Press, 2005. [doi:10.1145/1060590.1060675]

[2]   Sanjeev Arora and Rong Ge: New tools for graph coloring. In Proc. 14th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’11), pp. 1–12. Springer, 2011. [doi:10.1007/978-3-642-22935-0_1]

[3]   Sanjeev Arora, James Lee, and Assaf Naor: Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21(1):1–21, 2008. Preliminary version in STOC’05. [doi:10.1090/S0894-0347-07-00573-5, arXiv:math/0508154]

[4]   Sanjeev Arora, Satish Rao, and Umesh Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1–5:37, 2009. Preliminary version in STOC’04. [doi:10.1145/1502793.1502794]

[5]   Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, and Roy Schwartz: Min-Max graph partitioning and small set expansion. SIAM J. Comput., 43(2):872–904, 2014. Preliminary version in FOCS’11. [doi:10.1137/120873996, arXiv:1110.4319]

[6]   Ümit V. Çatalyürek and Cevdet Aykanat: Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication. IEEE Trans. Parallel and Distr. Systems, 10(7):673–693, 1999. Preliminary version in STOC’15. [doi:10.1109/71.780863, arXiv:1510.01520]

[7]   T-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang: Spectral properties of hypergraph laplacian and approximation algorithms, 2016. [arXiv:1605.01483]

[8]   Eden Chlamtáč, Konstantin Makarychev, and Yury Makarychev: How to play unique games using embeddings. In Proc. 47th FOCS, pp. 687–696. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.36]

[9]   Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, and Yuan Zhou: Approximation algorithms and hardness of the k-route cut problem. ACM Trans. Algorithms, 12(1):2:1–2:40, 2016. Preliminary version in SODA’12. [doi:10.1145/2644814, arXiv:1112.3611]

[10]   Karen D. Devine, Erik G. Boman, Robert T. Heaphy, Rob H. Bisseling, and Ümit V. Çatalyürek: Parallel hypergraph partitioning for scientific computing. In Proc. 20th Internat Parallel and Distr. Processing Symp. (IPDPS’06), 2006. [doi:10.1109/IPDPS.2006.1639359]

[11]   Shai Evra and Tali Kaufman: Bounded degree cosystolic expanders of every dimension. In Proc. 48th STOC, pp. 36–48. ACM Press, 2016. [doi:10.1145/2897518.2897543, arXiv:1510.00839]

[12]   Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629–657, 2008. Preliminary version in STOC’05. [doi:10.1137/05064299X]

[13]   George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar: Multilevel hypergraph partitioning: applications in VLSI domain. IEEE Trans. Very Large Scale Integration (VLSI) Systems, 7(1):69–79, 1999. Preliminary version in DAC’97. [doi:10.1109/92.748202]

[14]   Tali Kaufman, David Kazhdan, and Alexander Lubotzky: Ramanujan complexes and bounded degree topological expanders. In Proc. 55th FOCS, pp. 484–493. IEEE Comp. Soc. Press, 2014. [doi:10.1109/FOCS.2014.58]

[15]   Nathan Linial and Roy Meshulam: Homological connectivity of random 2-complexes. Combinatorica, 26(4):475–487, 2006. [doi:10.1007/s00493-006-0027-9]

[16]   Anand Louis: Hypergraph Markov operators, eigenvalues and approximation algorithms. In Proc. 47th STOC, pp. 713–722. ACM Press, 2015. [doi:10.1145/2746539.2746555, arXiv:1408.2425]

[17]   Anand Louis and Konstantin Makarychev: Approximation algorithm for sparsest k-partitioning. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 1244–1255. ACM Press, 2014. [doi:10.1137/1.9781611973402.92, arXiv:1306.4384]

[18]   Anand Louis and Yury Makarychev: Approximation algorithms for hypergraph small set expansion and small set vertex expansion. In Proc. 17th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’14), pp. 339–355. Springer, 2014. [doi:10.4230/LIPIcs.APPROX-RANDOM.2014.339, arXiv:1404.4575]

[19]   Anand Louis, Prasad Raghavendra, and Santosh Vempala: Private Communication, 2012.

[20]   Anand Louis, Prasad Raghavendra, and Santosh Vempala: The complexity of approximating vertex expansion. In Proc. 54th FOCS, pp. 360–369. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.46, arXiv:1304.3139]

[21]   Konstantin Makarychev and Yury Makarychev: Nonuniform graph partitioning with unrelated weights. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), pp. 812–822. Springer, 2014. [doi:10.1007/978-3-662-43948-7_67, arXiv:1401.0699]

[22]   Prasad Raghavendra and David Steurer: Graph expansion and the unique games conjecture. In Proc. 42nd STOC, pp. 755–764. ACM Press, 2010. [doi:10.1145/1806689.1806792]

[23]   Prasad Raghavendra, David Steurer, and Prasad Tetali: Approximations for the isoperimetric and spectral profile of graphs and related parameters. In Proc. 42nd STOC, pp. 631–640. ACM Press, 2010. [doi:10.1145/1806689.1806776]