Cardinality constrained minimum cut problems: complexity and algorithms
Cardinality constrained minimum cut problems: complexity and algorithms
复制标题
DOI：
10.1016/s0166-218x(03)00358-5
复制
发表时间：
2004-03-15
影响因子：
1.1
通讯作者：
Ehrgott, M
中科院分区：
文献类型：
--
作者：
Bruglieri, M;Maffioli, F;Ehrgott, M
在一些应用中，组合优化问题（COP）的解需要满足一个附加的基数约束，即包含固定数量的元素。到目前为止，对具有基数约束的COP族的研究还很少。本文解决了该类的一个新问题：k-基数最小割问题（k-card cut）。对于这个问题的许多变体，我们展示了最重要的图类的复杂性结果。此外，我们开发了几个启发式算法的k-卡切割问题的完全，完全二部图，和一般图。下界通过SDP公式得到，并用于显示启发式的质量。最后，给出了随机化SDP启发式算法和数值结果。(C) 2003 Elsevier B.V.版权所有
In several applications the solutions of combinatorial optimization problems (COP) are required to satisfy an additional cardinality constraint, that is to contain a fixed number of elements. So far the family of (COP) with cardinality constraints has been little investigated. The present work tackles a new problem of this class: the k-cardinality minimum cut problem (k-card cut). For a number of variants of this problem we show complexity results in the most significant graph classes. Moreover, we develop several heuristic algorithms for the k-card cut problem for complete, complete bipartite, and general graphs. Lower bounds are obtained through an SDP formulation, and used to show the quality of the heuristics. Finally, we present a randomized SDP heuristic and numerical results. (C) 2003 Elsevier B.V. All rights reserved.