论文标题
Min-Max $ K $ -CUT的固定参数近似方案
Fixed Parameter Approximation Scheme for Min-max $k$-cut
论文作者
论文摘要
我们考虑了Min-Max目标下的图形$ K $分区问题，称为Minmax $ k $ -cut。这里的输入是一个图$ g =（v，e）$，具有非负边权重$ W： w（δ（v_i））$。尽管最小化总和$ \ sum_ {i = 1}^k w（δ（v_i））$，称为Minsum $ k $ -cut，在文献中已广泛研究，但对最小化最大目标的最小化知之甚少。我们通过证明它是np-hard和w [1] - hard来启动Minmax $ k $ cut的研究，当通过$ k $进行参数化时，并在通过$ k $参数化时设计了参数化的近似方案。我们参数化近似方案的主要成分是Minmax $ k $ -cut的精确算法，该算法是在时间$ $ $（λk）^{o（k^2）} n^{o（1）} $中，其中$λ$是optimum的值，$ n $的值是$ n $的数量。我们的算法技术建立在Lokshtanov，Saurabh和Surianarayanan（Focs，2020）的技术基础上，他们在Minsum $ k $ -cut中显示出相似的结果。我们的算法技术更一般，可用于获得参数化的近似方案，以最大程度地减少每$ p \ geq 1 $的$ k $ - 分区的$ \ ell_p $ -Norm度量。
We consider the graph $k$-partitioning problem under the min-max objective, termed as Minmax $k$-cut. The input here is a graph $G=(V,E)$ with non-negative edge weights $w:E\rightarrow \mathbb{R}_+$ and an integer $k\geq 2$ and the goal is to partition the vertices into $k$ non-empty parts $V_1, \ldots, V_k$ so as to minimize $\max_{i=1}^k w(δ(V_i))$. Although minimizing the sum objective $\sum_{i=1}^k w(δ(V_i))$, termed as Minsum $k$-cut, has been studied extensively in the literature, very little is known about minimizing the max objective. We initiate the study of Minmax $k$-cut by showing that it is NP-hard and W[1]-hard when parameterized by $k$, and design a parameterized approximation scheme when parameterized by $k$. The main ingredient of our parameterized approximation scheme is an exact algorithm for Minmax $k$-cut that runs in time $(λk)^{O(k^2)}n^{O(1)}$, where $λ$ is value of the optimum and $n$ is the number of vertices. Our algorithmic technique builds on the technique of Lokshtanov, Saurabh, and Surianarayanan (FOCS, 2020) who showed a similar result for Minsum $k$-cut. Our algorithmic techniques are more general and can be used to obtain parameterized approximation schemes for minimizing $\ell_p$-norm measures of $k$-partitioning for every $p\geq 1$.
