Acta Scientiarum Naturalium Universitatis Pekinensis

Previous Articles     Next Articles

The Approximability of NP Optimization Problems

HUANG Xiong   

  1. Department of Computer Science and Technology, Peking University, Beijing, 100871
  • Received:1994-11-01 Online:1995-09-20 Published:1995-09-20

NP最优化问题的可近似性

黄雄   

  1. 北京大学计算机科学与技术系,北京,100871

Abstract: The approximability of NP optimization problems is investigated in this paper. We classify the problems according to their approximability and prove that these classes are different (under the hypothesis P≠NP). In addition, we define a reduction which preserves the approximation ratio among the problems, and find complete problems under this reduction for every class.

Key words: computational complexity, combinatorial optimization, NP completeness

摘要: 研究了NP最优化问题的可近似性。按照不同的可近似性将问题分类,证明了这些类是不同的 (在P≠NP的假设下),并定义了问题之间保持近似比的归约,为每一类找到了在此归约下完 全的问题。

关键词: 计算复杂性, 组合优化, NP完全性

CLC Number: