Most balanced minimum cuts and partially ordered knapsack
Most balanced minimum cuts and partially ordered knapsack
复制标题
最平衡的最小割和部分有序背包
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
P. Bonsma
中科院分区：
文献类型：
--
作者：
P. Bonsma
本文考虑了对给定的顶点s和t，根据不同的平衡准则，在最小st-边割和最小st-顶点割中寻找最平衡割的问题。对于边切割[S，S]，我们寻求最大化min{|S|, |S|}.对于G的顶点割C，我们考虑以下目标：（i）最大化min{|S|, |不|}，其中{S，T}是V（G）\C的一个划分，其中s ∈ S，t ∈ T且[S，T ] = n，（ii）最小化G-C的最大分支的阶，（iii）最大化G-C的最小分支的阶.所有这些问题都是NP难的。我们给出了一个PTAS的边缘切割变体和（i）。我们给一个2-近似（ii），并表明，没有非平凡的近似存在（iii），除非P=NP。为了证明这些结果，我们证明了我们可以对G的顶点进行划分，并在划分的子集上定义一个偏序，使得偏序的理想双射对应于G的最小st-割.这表明这些问题与均匀偏序背包（UPOK）密切相关，这是POK的一种变体，其中元素效用等于元素权重。我们的PTAS也是用于特殊类型的UPOK实例的PTAS。
We consider the problem of finding most balanced cuts among minimum st-edge cuts and minimum st-vertex cuts, for given vertices s and t, according to different balance criteria. For edge cuts [S, S] we seek to maximize min{|S|, |S|}. For vertex cuts C of G we consider the objectives of (i) maximizing min{|S|, |T |}, where {S, T} is a partition of V (G)\C with s ∈ S, t ∈ T and [S, T ] = ∅, (ii) minimizing the order of the largest component of G−C, and (iii) maximizing the order of the smallest component of G−C. All of these problems are shown to be NP-hard. We give a PTAS for the edge cut variant and for (i). We give a 2-approximation for (ii), and show that no non-trivial approximation exists for (iii) unless P=NP. To prove these results we show that we can partition the vertices of G, and define a partial order on the subsets of the partition, such that ideals of the partial order correspond bijectively to minimum st-cuts of G. This shows that the problems are closely related to Uniform Partially Ordered Knapsack (UPOK), a variant of POK where element utilities are equal to element weights. Our PTAS is also a PTAS for special types of UPOK instances.