Approximation Algorithm for Norm Multiway Cut

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

Research output: Chapter in Book/Report/Conference proceedingConference 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(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.

Original languageEnglish (US)
Title of host publication31st Annual European Symposium on Algorithms, ESA 2023
EditorsInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772952
DOIs
StatePublished - Sep 2023
Event31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands
Duration: Sep 4 2023Sep 6 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume274
ISSN (Print)1868-8969

Conference

Conference31st Annual European Symposium on Algorithms, ESA 2023
Country/TerritoryNetherlands
CityAmsterdam
Period9/4/239/6/23

Keywords

  • Approximation algorithms
  • Multiway cut

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Approximation Algorithm for Norm Multiway Cut'. Together they form a unique fingerprint.

Cite this