On the Hardness of Approximating the $k$-Way Hypergraph Cut problem

by Chandra Chekuri and Shi Li

Theory of Computing, Volume 16(14), pp. 1-8, 2020

Bibliography with links to cited articles

[1]   Aditya Bhaskara, Moses Charikar, Eden Chlamtác, Uriel Feige, and Aravindan Vijayaraghavan: Detecting high log-densities: An O(n14) approximation for densest k-subgraph. In Proc. 42nd STOC, pp. 201–210. ACM Press, 2010. [doi:10.1145/1806689.1806719, arXiv:1001.2891]

[2]   Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Zhou: Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph. In Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’12), pp. 388–405. ACM Press, 2012. [doi:10.1137/1.9781611973099.34, arXiv:1110.1360]

[3]   Karthekeyan Chandrasekaran and Chandra Chekuri: Hypergraph k-cut for fixed k in deterministic polynomial time. In Proc. 61st FOCS, pp. 810–821. IEEE Comp. Soc. Press, 2020. [doi:10.1109/FOCS46700.2020.00080, arXiv:2009.12442]

[4]   Karthekeyan Chandrasekaran, Chao Xu, and Xilin Yu: Hypergraph k-cut in randomized polynomial time. Math. Programming, 2019:1–29. Preliminary version in SODA’18. [doi:10.1007/s10107-019-01443-7]

[5]   Chandra Chekuri and Alina Ene: Approximation algorithms for submodular multiway partition. In Proc. 52nd FOCS, pp. 807–816. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.34, arXiv:1105.2048]

[6]   Chandra Chekuri, Kent Quanrud, and Chao Xu: LP relaxation and tree packing for minimum k-cut. SIAM J. Discrete Math., 34(2):1334–1353, 2020. Preliminary version in SOSA’19. [doi:10.1137/19M1299359, arXiv:1808.05765]

[7]   Alina Ene, Jan Vondrák, and Yi Wu: Local distribution and the symmetry gap: Approximability of multiway partitioning problems. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 306–325. ACM Press, 2013. [doi:10.1137/1.9781611973105.23, arXiv:1503.03905]

[8]   Olivier P. Goldschmidt and Dorit S. Hochbaum: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res., 19(1):24–37, 1994. [doi:10.1287/moor.19.1.24]

[9]   Flavio Guíńez and Maurice Queyranne: The size-constrained submodular k-partition problem. Unpublished manuscript. Available on Google Docs. See also slides on author’s home page, 2012.

[10]   Anupam Gupta, David G. Harris, Euiwoong Lee, and Jason Li: Optimal bounds for the k-cut problem, 2020. [arXiv:2005.08301]

[11]   Subhash Khot: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput., 36(4):1025–1071, 2006. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447037]

[12]   Pasin Manurangsi: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In Proc. 49th STOC, pp. 954–961. ACM Press, 2017. [doi:10.1145/3055399.3055412, arXiv:1611.05991]

[13]   Pasin Manurangsi: Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the Small Set Expansion Hypothesis. Algorithms, 11(1):1–10, 2018. Preliminary version in ICALP’17. [doi:10.3390/a11010010]

[14]   Kazumasa Okumoto, Takuro Fukunaga, and Hiroshi Nagamochi: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica, 62(3):787–806, 2012. Preliminary version in ISAAC’09. [doi:10.1007/s00453-010-9483-0]

[15]   Maurice Queyranne: On optimum size-constrained set partitions. In Abstracts, Combinatorial Optimization Workshop, AUSSOIS, 1999. AUSSOIS.

[16]   Richard Santiago: Multi-Agent Submodular Optimization: Variations and Generalizations. Ph. D. thesis, McGill University, 2019. LINK at eScholarship@McGill.

[17]   Huzur Saran and Vijay V. Vazirani: Finding k-cuts within twice the optimal. SIAM J. Comput., 24(1):101–108, 1995. Preliminary version in FOCS’91. [doi:10.1137/S0097539792251730]

[18]   Mingyu Xiao: Finding minimum 3-way cuts in hypergraphs. Inform. Process. Lett., 110(14-15):554–558, 2010. Preliminary version in TAMC’08. [doi:10.1016/j.ipl.2010.05.003]

[19]   Liang Zhao, Hiroshi Nagamochi, and Toshihide Ibaraki: Greedy splitting algorithms for approximating multiway partition problems. Math. Programming, 102(1):167–183, 2005. [doi:10.1007/s10107-004-0510-2]