Approximation Algorithm for Norm Multiway Cut

Charlie Carlson; Jafar Jafarov; Konstantin Makarychev; Yury Makarychev; Liren Shan

doi:10.4230/LIPIcs.ESA.2023.32

Approximation Algorithm for Norm Multiway Cut

Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, Liren Shan

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced ℓ_p-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the ℓ_p norm of the edge boundaries of k parts. We provide an O(log^1/2 n log^1/2+1/p k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log^3/2 n log^1/2 k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log^1/2 nlog^7/2 k) approximation algorithm with a weaker oracle and an O(log^1/2 nlog^5/2 k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n^1/4−ε approximation algorithm for every ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture.

Original language	English (US)
Title of host publication	31st Annual European Symposium on Algorithms, ESA 2023
Editors	Inge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959772952
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2023.32
State	Published - Sep 2023
Event	31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands Duration: Sep 4 2023 → Sep 6 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	274
ISSN (Print)	1868-8969

Conference

Conference	31st Annual European Symposium on Algorithms, ESA 2023
Country/Territory	Netherlands
City	Amsterdam
Period	9/4/23 → 9/6/23

Funding

Funding Konstantin Makarychev: supported by NSF Awards CCF-1955351, CCF-1934931, EECS-2216970. Yury Makarychev: supported by NSF CCF-1955173, CCF-1934843, and ECCS-2216899. Liren Shan: supported by NSF Awards CCF-1955351, CCF-1934931, and EECS-2216970.

Keywords

Approximation algorithms
Multiway cut

ASJC Scopus subject areas

Software

Access to Document

10.4230/LIPIcs.ESA.2023.32

Cite this

Carlson, C., Jafarov, J., Makarychev, K., Makarychev, Y., & Shan, L. (2023). Approximation Algorithm for Norm Multiway Cut. In I. Li Gortz, M. Farach-Colton, S. J. Puglisi, & G. Herman (Eds.), 31st Annual European Symposium on Algorithms, ESA 2023 Article 32 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 274). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2023.32

Carlson, Charlie ; Jafarov, Jafar ; Makarychev, Konstantin et al. / Approximation Algorithm for Norm Multiway Cut. 31st Annual European Symposium on Algorithms, ESA 2023. editor / Inge Li Gortz ; Martin Farach-Colton ; Simon J. Puglisi ; Grzegorz Herman. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{ac109af92d0b43c4bad345e88fbc69a4,

title = "Approximation Algorithm for Norm Multiway Cut",

abstract = "We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced ℓp-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the ℓp norm of the edge boundaries of k parts. We provide an O(log1/2 n log1/2+1/p k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log3/2 n log1/2 k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log1/2 nlog7/2 k) approximation algorithm with a weaker oracle and an O(log1/2 nlog5/2 k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n1/4−ε approximation algorithm for every ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture.",

keywords = "Approximation algorithms, Multiway cut",

author = "Charlie Carlson and Jafar Jafarov and Konstantin Makarychev and Yury Makarychev and Liren Shan",

note = "Publisher Copyright: {\textcopyright} Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan.; 31st Annual European Symposium on Algorithms, ESA 2023 ; Conference date: 04-09-2023 Through 06-09-2023",

year = "2023",

month = sep,

doi = "10.4230/LIPIcs.ESA.2023.32",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "{Li Gortz}, Inge and Martin Farach-Colton and Puglisi, {Simon J.} and Grzegorz Herman",

booktitle = "31st Annual European Symposium on Algorithms, ESA 2023",

}

Carlson, C, Jafarov, J, Makarychev, K, Makarychev, Y & Shan, L 2023, Approximation Algorithm for Norm Multiway Cut. in I Li Gortz, M Farach-Colton, SJ Puglisi & G Herman (eds), 31st Annual European Symposium on Algorithms, ESA 2023., 32, Leibniz International Proceedings in Informatics, LIPIcs, vol. 274, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 31st Annual European Symposium on Algorithms, ESA 2023, Amsterdam, Netherlands, 9/4/23. https://doi.org/10.4230/LIPIcs.ESA.2023.32

Approximation Algorithm for Norm Multiway Cut. / Carlson, Charlie; Jafarov, Jafar; Makarychev, Konstantin et al.
31st Annual European Symposium on Algorithms, ESA 2023. ed. / Inge Li Gortz; Martin Farach-Colton; Simon J. Puglisi; Grzegorz Herman. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 32 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 274).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximation Algorithm for Norm Multiway Cut

AU - Carlson, Charlie

AU - Jafarov, Jafar

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Shan, Liren

N1 - Publisher Copyright: © Charlie Carlson, Jafar Jafarov, Konstantin Makarychev, Yury Makarychev, and Liren Shan.

PY - 2023/9

Y1 - 2023/9

N2 - We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced ℓp-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the ℓp norm of the edge boundaries of k parts. We provide an O(log1/2 n log1/2+1/p k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log3/2 n log1/2 k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log1/2 nlog7/2 k) approximation algorithm with a weaker oracle and an O(log1/2 nlog5/2 k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n1/4−ε approximation algorithm for every ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture.

AB - We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced ℓp-norm Multiway Cut, a generalization of the problem, in which the goal is to minimize the ℓp norm of the edge boundaries of k parts. We provide an O(log1/2 n log1/2+1/p k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log3/2 n log1/2 k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log1/2 nlog7/2 k) approximation algorithm with a weaker oracle and an O(log1/2 nlog5/2 k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n1/4−ε approximation algorithm for every ε > 0 assuming the Hypergraph Dense-vs-Random Conjecture.

KW - Approximation algorithms

KW - Multiway cut

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

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

U2 - 10.4230/LIPIcs.ESA.2023.32

DO - 10.4230/LIPIcs.ESA.2023.32

M3 - Conference contribution

AN - SCOPUS:85173481773

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 31st Annual European Symposium on Algorithms, ESA 2023

A2 - Li Gortz, Inge

A2 - Farach-Colton, Martin

A2 - Puglisi, Simon J.

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st Annual European Symposium on Algorithms, ESA 2023

Y2 - 4 September 2023 through 6 September 2023

ER -

Carlson C, Jafarov J, Makarychev K, Makarychev Y, Shan L. Approximation Algorithm for Norm Multiway Cut. In Li Gortz I, Farach-Colton M, Puglisi SJ, Herman G, editors, 31st Annual European Symposium on Algorithms, ESA 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 32. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.ESA.2023.32

Approximation Algorithm for Norm Multiway Cut

Abstract

Publication series

Conference

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this