$$\ell _p$$-Norm Multiway Cut
$$\ell _p$$-Norm Multiway Cut
复制标题
$$ell _p$$-范数多路剪切
DOI：
10.1007/s00453-022-00983-3
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
Wang, Weihang
中科院分区：
文献类型：
--
作者：
Chandrasekaran, Karthekeyan;Wang, Weihang
我们引入并研究了-norm-multiway-cut：这里的输入是一个无向图，它的边权沿着为k个端点，目标是在k个部分中找到顶点集的一个划分，每个部分恰好包含一个端点，从而使这些部分的割值的-norm最小化。这是min-sum multiway cut（when）和min-max multiway cut（when）的统一推广，这两个问题都是图划分文献中研究得很好的经典问题。我们证明了-norm-multiway-cut是NP-难的常数终端数和NP-难的平面图。在算法方面，我们设计了一个近似。我们还证明了一个自然凸规划的完整性缺口和一个不可逼近的任何常数tassuming小集扩张假设。
We introduce and study-norm-multiway-cut: the input here is an undirected graph with non-negative edge weights along withkterminals and the goal is to find a partition of the vertex set intokparts each containing exactly one terminal so as to minimize the-norm of the cut values of the parts. This is a unified generalization of min-sum multiway cut (when) and min–max multiway cut (when), both of which are well-studied classic problems in the graph partitioning literature. We show that-norm-multiway-cutis NP-hard for constant number of terminals and is NP-hard in planar graphs. On the algorithmic side, we design an-approximation for all. We also show an integrality gap offor a natural convex program and an-inapproximability for any constantassuming the small set expansion hypothesis.