p -Norm Multiway Cut

Research output: Contribution to journalArticlepeer-review

Abstract

We introduce and study ℓp-norm-multiway-cut: the input here is an undirected graph with non-negative edge weights along with k terminals and the goal is to find a partition of the vertex set into k parts each containing exactly one terminal so as to minimize the ℓp-norm of the cut values of the parts. This is a unified generalization of min-sum multiway cut (when p= 1) and min–max multiway cut (when p= ∞), both of which are well-studied classic problems in the graph partitioning literature. We show that ℓp-norm-multiway-cut is NP-hard for constant number of terminals and is NP-hard in planar graphs. On the algorithmic side, we design an O(log 1.5nlog 0.5k) -approximation for all p≥ 1. We also show an integrality gap of Ω (k1-1/p) for a natural convex program and an O(k1-1/p-ϵ) -inapproximability for any constant ϵ> 0 assuming the small set expansion hypothesis.

Original languageEnglish (US)
Pages (from-to)2667-2701
Number of pages35
JournalAlgorithmica
Volume84
Issue number9
DOIs
StatePublished - Sep 2022

Keywords

  • Approximation algorithms
  • Multiway cut

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'ℓp -Norm Multiway Cut'. Together they form a unique fingerprint.

Cite this