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 - https://www.scopus.com/pages/publications/85173481773
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 -