2026-07-21T14:16:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14610 2024-03-06T10:54:26Z ddc:004 open_access

𝓁_p-Norm Multiway Cut Chandrasekaran, Karthekeyan Wang, Weihang multiway cut approximation algorithms 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² n)-approximation for all p ≥ 1. We also show an integrality gap of Ω(k^{1-1/p}) for a natural convex program and an O(k^{1-1/p-ε})-inapproximability for any constant ε > 0 assuming the small set expansion hypothesis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karthekeyan Chandrasekaran and Weihang Wang 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.29 urn:nbn:de:0030-drops-146103 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.29 eng https://creativecommons.org/licenses/by/4.0/legalcode