Approximation Algorithms for Norm Multiway Cut

2023/08/16 by Carlson, Charlie, Jafarov, Jafar, Makarychev, Konstantin +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2308.08373

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, 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.

Related

• ℓ_p-norm Multiway Cut
• On Multiway Cut parameterized above lower bounds
• Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
• Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds
• Improving the Integrality Gap for Multiway Cut