A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts
A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts
复制标题
多准则全局最小割的强多项式时间算法
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Queyranne
中科院分区：
文献类型：
--
作者：
Hassene Aissi;A. Ridha Mahjoub;S. T. McCormick;M. Queyranne
我们研究了全球最小切割问题的两批位，其中每个边缘通过两个非负成本函数评估。当我们采用标准的所有凸组合时，这种问题的参数复杂性是参数曲线中的线性段数。我们证明了全局最小切割问题的参数复杂性是O（| V | 3）。结果，我们表明非主导点的数量为O（| V | 7），并给出第一个强烈多项式时间算法来计算这些点。这些结果显着改善了Mulmuley [11]给出的参数复杂性的超级顺序结合，以及Armon和Zwick [1]的伪多项式时间算法，以解决这一双核问题。我们将其中一些结果扩展到任意成本函数和两个以上的标准，以及超图中的全球最小削减。
We investigate the bicriteria global minimum cut problem where each edge is evaluated by two nonnegative cost functions. The parametric complexity of such a problem is the number of linear segments in the parametric curve when we take all convex combinations of the criteria. We prove that the parametric complexity of the global minimum cut problem is O(|V|3). As a consequence, we show that the number of non-dominated points is O(|V|7) and give the first strongly polynomial time algorithm to compute these points. These results improve on significantly the super-polynomial bound on the parametric complexity given by Mulmuley [11], and the pseudo-polynomial time algorithm of Armon and Zwick [1] to solve this bicriteria problem. We extend some of these results to arbitrary cost functions and more than two criteria, and to global minimum cuts in hypergraphs.