2026-07-28T06:31:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18685 2024-03-06T11:02:27Z ddc:004 open_access

Approximation Algorithm for Norm Multiway Cut Carlson, Charlie Jafarov, Jafar Makarychev, Konstantin Makarychev, Yury Shan, Liren Multiway cut Approximation algorithms 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} nlog^{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} n log^{7/2} k) approximation algorithm with a weaker oracle and an O(log^{1/2} n log^{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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Charlie Carlson and Jafar Jafarov and Konstantin Makarychev and Yury Makarychev and Liren Shan 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.32 urn:nbn:de:0030-drops-186854 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.32 eng https://creativecommons.org/licenses/by/4.0/legalcode