论文标题
从P到NP硬度的过渡：线性排序问题的情况
Transitions from P to NP-hardness: the case of the Linear Ordering Problem
论文作者
论文摘要
在本文中，我们评估了问题从P转到NP- hard时的建设性启发式方法。这是通过线性排序问题完成的。更具体地说，对于此问题，我们证明目标函数可以表示为两个目标函数的总和，其中一个与P问题相关联（提出了确切的多项式时间算法来求解它），而另一个目标算法则与NP-HARD问题有关。我们研究了不同的行为仅取决于单变量信息的不同建设性算法取决于问题的P或NP-HARD组件的贡献。进行了许多实验，以减小的尺寸进行，其中已知的问题的全局最佳最优值，给NP-HARD组件的权重不同，而P组分的重量是固定的。观察到建设性算法的性能如何变得更糟，因为给予NP-HARD组件的重量增加。
In this paper we evaluate how constructive heuristics degrade when a problem transits from P to NP-hard. This is done by means of the linear ordering problem. More specifically, for this problem we prove that the objective function can be expressed as the sum of two objective functions, one of which is associated with a P problem (an exact polynomial time algorithm is proposed to solve it), while the other is associated with an NP-hard problem. We study how different constructive algorithms whose behaviour only depends on univariate information perform depending on the contribution of the P or NP-hard components of the problem. A number of experiments are conducted with reduced dimensions, where the global optimum of the problems is known, giving different weights to the NP-hard component, while the weight of the P component is fixed. It is observed how the performance of the constructive algorithms gets worse as the weight given to the NP-hard component increases.
