组合最优化与计算复杂性综述  

Review on Combinatorial Optimization and Computational Complexity

作　　者：王继强[1] WANG Ji-qiang（School of Mathematics and Quantitative Economics,Shandong University of Finance and Economics,Jinan 250014,China）

机构地区：[1]山东财经大学数学与数量经济学院,山东济南250014

出　　处：《电脑知识与技术》2013年第5期3140-3141,共2页Computer Knowledge and Technology

基　　金：山东省自然科学基金（ZR2011FQ024）资助

摘　　要：综合论述了组合最优化理论与计算复杂性理论,尤其是NP-完备理论之间的密切关系,揭示出NP-完备理论研究的重大理论和现实意义。The close relationship between theory of combinatorial optimization and theory of computational complexity,especially theory of NP-complete,is reviewed,and significant theoretical and practical importance for theory of NP-complete is discussed.

关 键 词：组合最优化 计算复杂性 NP-完备 近似算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]