TY - JOUR

T1 - Improving the integrality gap for multiway cut

AU - Bérczi, Kristóf

AU - Chandrasekaran, Karthekeyan

AU - Király, Tamás

AU - Madan, Vivek

N1 - Funding Information:
Krist?f B?rczi was supported by the J?nos Bolyai Research Fellowship of the Hungarian Academy of Sciences and by the ?NKP-18-4 New National Excellence Program of the Ministry of Human Capacities. Karthik is supported by NSF grants CCF-1907937 and CCF-1814613. Tam?s was supported by the Hungarian National Research, Development and Innovation Office ? NKFIH grant K120254. Vivek was supported by the NSF Grant CCF-1319376. Projects No. NKFI-128673 and No. ED_18-1-2019-0030 (Application-specific highly reliable IT solutions) have been implemented with the support provided from the National Research, Development and Innovation Fund of Hungary, financed under the FK_18 and the Thematic Excellence Programme funding schemes, respectively.
Funding Information:
Kristóf Bérczi was supported by the János Bolyai Research Fellowship of the Hungarian Academy of Sciences and by the ÚNKP-18-4 New National Excellence Program of the Ministry of Human Capacities. Karthik is supported by NSF grants CCF-1907937 and CCF-1814613. Tamás was supported by the Hungarian National Research, Development and Innovation Office – NKFIH grant K120254. Vivek was supported by the NSF Grant CCF-1319376. Projects No. NKFI-128673 and No. ED_18-1-2019-0030 (Application-specific highly reliable IT solutions) have been implemented with the support provided from the National Research, Development and Innovation Fund of Hungary, financed under the FK_18 and the Thematic Excellence Programme funding schemes, respectively.

PY - 2020/9/1

Y1 - 2020/9/1

N2 - In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal, so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k≥ 3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák (Proceedings of the forty-sixth annual ACM symposium on theory of computing, STOC, 2014) while the best known inapproximability result due to Angelidakis et al. (Integer programming and combinatorial optimization, IPCO, 2017) rules out efficient algorithms to achieve an approximation factor less than 1.2 under the unique games conjecture (UGC). In this work, we improve the lower bound to 1.20016 under UGC by constructing an integrality gap instance for the CKR relaxation. The CKR relaxation embeds the graph into a simplex and it is known that its integrality gap translates to inapproximability under UGC. A technical challenge in improving the integrality gap has been the lack of geometric tools to understand higher-dimensional simplices. Our instance is a non-trivial 3-dimensional instance that overcomes this technical challenge. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. We believe that this technique could be exploited further to construct instances with larger integrality gap. One of the ingredients of our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák (Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, SODA, 2015) that might be of independent combinatorial interest.

AB - In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal, so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k≥ 3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák (Proceedings of the forty-sixth annual ACM symposium on theory of computing, STOC, 2014) while the best known inapproximability result due to Angelidakis et al. (Integer programming and combinatorial optimization, IPCO, 2017) rules out efficient algorithms to achieve an approximation factor less than 1.2 under the unique games conjecture (UGC). In this work, we improve the lower bound to 1.20016 under UGC by constructing an integrality gap instance for the CKR relaxation. The CKR relaxation embeds the graph into a simplex and it is known that its integrality gap translates to inapproximability under UGC. A technical challenge in improving the integrality gap has been the lack of geometric tools to understand higher-dimensional simplices. Our instance is a non-trivial 3-dimensional instance that overcomes this technical challenge. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. We believe that this technique could be exploited further to construct instances with larger integrality gap. One of the ingredients of our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák (Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, SODA, 2015) that might be of independent combinatorial interest.

KW - Approximation

KW - Combinatorial optimization

KW - Integrality gap

KW - Multiway cut

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

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

U2 - 10.1007/s10107-020-01485-2

DO - 10.1007/s10107-020-01485-2

M3 - Article

AN - SCOPUS:85081629733

VL - 183

SP - 171

EP - 193

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -