Easy and difficult objective functions for max cut
Easy and difficult objective functions for max cut
复制标题
DOI：
10.1007/s10107-002-0328-8
复制
发表时间：
2003
影响因子：
2.7
通讯作者：
S. McCormick;M. Rao;G. Rinaldi
中科院分区：
文献类型：
--
作者：
S. McCormick;M. Rao;G. Rinaldi
本文研究了多项式可解最大割和NP硬最大割实例之间的边界，当它们仅基于目标函数系数的符号模式进行分类时，即，包含目标函数向量的正形的。事实证明，由正边诱导的子图的匹配数是使我们能够区分问题的多项式可解实例和困难实例的关键参数。我们给出了多项式可解情形的一些应用。
This note investigates the boundary between polynomially-solvable Max Cut and NP Hard Max Cut instances when they are classified only on the basis of the sign pattern of the objective function coefficients, i.e., of the orthant containing the objective function vector. It turns out that the matching number of the subgraph induced by the positive edges is the key parameter that allows us to differentiate between polynomially-solvable and hard instances of the problem. We give some applications of the polynomially solvable cases.