论文部分内容阅读
Lawler和Lenstra已证明:单机排序问题1‖n∑q=1Wqmax(cq-dq),0)是“强”NP完全的,而该问题是1‖n∑q=1Wqcq-dq的子问题,因而也是强NP完全问题,没有好算法,本文在假设Pk≥Pq→Pk/Wk〉Pq/Wq成立的条件下,设计出求该问题的近似最优解的伪多项式时间算法。