A simple algorithm for the multiway cut problem. (English) Zbl 1476.90336
Summary: Multiway Cut is a classic graph partitioning problem in which the goal is to disconnect a given set of special vertices called terminals. This problem admits a rich sequence of works. Unfortunately, most of these works resort to the mix of multiple algorithmic components, resulting in both complicated algorithms and analysis. We present a simple algorithm for the Multiway Cut problem that is comprised of a single algorithmic component and achieves an approximation of \(\frac{11}{8} = 1.375\).
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C22 | Signed and weighted graphs |
| 05C40 | Connectivity |
References:
| [1] | Haris Angelidakis, Yury Makarychev, Pasin Manurangsi, An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut, in: Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO, 2017, Waterloo, on, Canada, June 26-28, 2017, Proceedings, 2017, pp. 39-50. · Zbl 1418.90267 |
| [2] | Arora, Sanjeev; Karger, David; Karpinski, Marek, (Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems, STOC ’95 (1995)), 284-293 · Zbl 0968.68534 |
| [3] | Arora, Sanjeev; Rao, Satish; Vazirani, Umesh, Expander flows, geometric embeddings and graph partitioning, J. ACM, 56, 2, 5:1-5:37 (2009) · Zbl 1325.68255 |
| [4] | Aumann, Yonatan; Rabani, Yuval, An \(O ( \log k )\) approximate min-cut max-flow theorem and approximation algorithm, SIAM J. Comput., 27, 1, 291-301 (1998) · Zbl 0910.05038 |
| [5] | Bérczi, Kristóf; Chandrasekaran, Karthekeyan; Király, Tamás; Lee, Euiwoong; Xu, Chao, Global and fixed-terminal cuts in digraphs, CoRR, abs/1612.00156 (2016) · Zbl 1417.05084 |
| [6] | Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan, Improving the integrality gap for multiway cut, in: Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO, 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings, 2019, pp. 115-127. · Zbl 1403.68148 |
| [7] | Niv Buchbinder, Joseph (Seffi) Naor, Roy Schwartz, Simplex partitioning via exponential clocks and the multiway cut problem, in: Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, 2013, pp. 535-544. · Zbl 1293.05286 |
| [8] | Niv Buchbinder, Roy Schwartz, Baruch Weizman, Simplex Transformations and the Multiway Cut Problem, in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, 2017, pp. 2400-2410. · Zbl 1410.05193 |
| [9] | Călinescu, Gruia; Karloff, Howard J.; Rabani, Yuval, An improved approximation algorithm for MULTIWAY CUT, J. Comput. System Sci., 60, 3, 564-574 (2000) · Zbl 0986.90043 |
| [10] | Călinescu, Gruia; Karloff, Howard; Rabani, Yuval, (Approximation Algorithms for the 0-Extension Problem. Approximation Algorithms for the 0-Extension Problem, SODA ’01 (2001)), 8-16 · Zbl 0987.05086 |
| [11] | Cunningham, William H.; Tang, Lawrence, (Optimal 3-Terminal Cuts and Linear Programming. Optimal 3-Terminal Cuts and Linear Programming, IPCO ’09 (1999)), 114-125 · Zbl 0948.90159 |
| [12] | Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M., The complexity of multiterminal cuts, SIAM J. Comput., 23, 864-894 (1994) · Zbl 0809.68075 |
| [13] | Even, Guy; Naor, Joseph Seffi; Rao, Satish; Schieber, Baruch, Divide-and-conquer approximation algorithms via spreading metrics, J. ACM, 47, 4, 585-616 (2000) · Zbl 1303.68156 |
| [14] | Fakcharoenphol, Jittat; Harrelson, Chris; Rao, Satish; Talwar, Kunal, (An Improved Approximation Algorithm for the 0-Extension Problem. An Improved Approximation Algorithm for the 0-Extension Problem, SODA ’03 (2003)), 257-265 · Zbl 1094.68701 |
| [15] | Fakcharoenphol, Jittat; Rao, Satish; Talwar, Kunal, A tight bound on approximating arbitrary metrics by tree metrics, J. Comput. System Sci., 69, 3, 485-497 (2004) · Zbl 1071.68082 |
| [16] | Freund, Ari; Karloff, Howard J., A lower bound of 8/(7+(1/k-1)) on the integrality ratio of the Calinescu-Karloff-Rabani relaxation for multiway cut, Inf. Process. Lett., 75, 1-2, 43-50 (2000) · Zbl 1339.68204 |
| [17] | Frieze, Alan M.; Kannan, Ravi, (The Regularity Lemma and Approximation Schemes for Dense Problems. The Regularity Lemma and Approximation Schemes for Dense Problems, FOCS ’96 (1996)), 12-20 |
| [18] | Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis, Approximate max-flow min-(multi)cut theorems and their applications, SIAM J. Comput., 25, 698-707 (1993) · Zbl 1310.05198 |
| [19] | Garg, Naveen; Vazirani, Vijay V.; Yannakakis, Mihalis, Multiway cuts in node weighted graphs, J. Algorithms, 50, 1, 49-61 (2004) · Zbl 1068.68178 |
| [20] | Goemans, Michel X.; Williamson, David P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 6, 1115-1145 (1995) · Zbl 0885.68088 |
| [21] | Karger, David R.; Klein, Philip N.; Stein, Clifford; Thorup, Mikkel; Young, Neal E., Rounding algorithms for a geometric embedding of minimum multiway cut, Math. Oper. Res., 29, 3, 436-461 (2004) · Zbl 1082.90149 |
| [22] | Karzanov, Alexander V., Minimum 0-extensions of graph metrics, European J. Combin., 19, 1, 71-101 (1998) · Zbl 0894.90147 |
| [23] | Khot, Subhash; Regev, Oded, Vertex cover might be hard to approximate to within \(2- \epsilon \), J. Comput. System Sci., 74, 3, 335-349 (2008) · Zbl 1133.68061 |
| [24] | Leighton, Tom; Rao, Satish, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM, 46, 6, 787-832 (1999) · Zbl 1065.68666 |
| [25] | Linial, Nathan; London, Eran; Rabinovich, Yuri, The geometry of graphs and some of its algorithmic applications, Combinatorica, 15, 2, 215-245 (1995) · Zbl 0827.05021 |
| [26] | Manokaran, Rajsekar; Naor, Joseph (Seffi); Raghavendra, Prasad; Schwartz, Roy, (SDP Gaps and UGC Hardness for Multiway Cut, 0-Extension, and Metric Labeling. SDP Gaps and UGC Hardness for Multiway Cut, 0-Extension, and Metric Labeling, STOC ’08 (2008)), 11-20 · Zbl 1231.68140 |
| [27] | Naor, Joseph; Zosin, Leonid, A 2-approximation algorithm for the directed multiway cut problem, SIAM J. Comput., 31, 2, 477-482 (2001) · Zbl 1052.68103 |
| [28] | Ankit Sharma, Jan Vondrák, Multiway cut, pairwise realizable distributions, and descending thresholds, in: Symposium on Theory of Computing, STOC 2014, 2014, pp. 724-733. · Zbl 1315.68288 |
| [29] | Vazirani, Vijay V., Approximation algorithms (2001), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 1138.90417 |
| [30] | Williamson, David P.; Shmoys, David B., The design of approximation algorithms (2011), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 1219.90004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
