单机排序问题1Pk≥Pq→Pk／Wp〉Pq／Wqn∑q=1WqCq—dq近似…

摘要

Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明：单机排序问题１‖ｎ∑ｑ＝１Ｗｑｍａｘ（ｃｑ－ｄｑ），０）是“强”ＮＰ完全的，而该问题是１‖ｎ∑ｑ＝１Ｗｑｃｑ－ｄｑ的子问题，因而也是强ＮＰ完全问题，没有好算法，本文在假设Ｐｋ≥Ｐｑ→Ｐｋ／Ｗｋ〉Ｐｑ／Ｗｑ成立的条件下，设计出求该问题的近似最优解的伪多项式时间算法。