单机排序问题1｜P_k≥P_qP_k／W_k＞P_q／W_q｜sum　from　q＝1　to　n　of　（…）W_q｜c_q－d_q｜近似最优解的伪多项式时间算法

作     者：杨汉兴 

出 版 物：《武汉冶金科技大学学报》 (Journal of Wuhan University of Science and Technology)

年 卷 期：1996年第19卷第3期

页      码：362-371页

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

主 题 词：伪多项式时间 排序 近似最优解 计算方法 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

馆 藏 号：203993543...