NP组合优化近似计算的难度  

The Hardness of Approximate Computation in NP Combinatorial Optimization

作　　者：张立昂[1] 

机构地区：[1]北京大学计算机科学技术系

出　　处：《数学理论与应用》1999年第3期60-66,共7页Mathematical Theory and Applications

基　　金：九五国家重点科技攻关项目;北京大学自然科学预研基金

摘　　要：本文扼要介绍近二十年来在组合优化可近似性的研究方面所取得的进展，包括不可近似性的证明，对组合优化问题用逻辑描述的语法分类及其可近似性．In this paper,we presented the progress of approximate computation in combinatorial optimization in the recent twenty years,and which included the provety of non-approximability,and classed the problems of combinatorial optimization in the program of logical discussion and their approximation.

关 键 词：组合优化 NP难的 可近似性 

分 类 号：O224[理学—运筹学与控制论]