NP最优化问题的可近似性

北京大学学报（自然科学版）

NP最优化问题的可近似性

黄雄

北京大学计算机科学与技术系，北京，100871

收稿日期:1994-11-01 出版日期:1995-09-20 发布日期:1995-09-20

The Approximability of NP Optimization Problems

HUANG Xiong

Department of Computer Science and Technology, Peking University, Beijing, 100871

Received:1994-11-01 Online:1995-09-20 Published:1995-09-20

摘要/Abstract

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

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

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

中图分类号: