| 组合优化若干经典问题新进展 |
| |
| 引用本文： | 陈旭瑾,徐大川,张国川.组合优化若干经典问题新进展[J].运筹学学报,2014,18(1):149-158. |
| |
| 作者姓名： | 陈旭瑾 徐大川 张国川 |
| |
| 作者单位： | 1. 中国科学院数学与系统科学研究院应用数学所, 北京 100190; 2. 北京工业大学应用数理学院, 北京 100124； 3. 浙江大学计算机科学与技术学院, 杭州 310027 |
| |
| 基金项目： | 国家自然科学基金(Nos.11222109,11371001,11271325) |
| |
| 摘 要： | 组合优化是20世纪中后期发展起来的一个运筹学与计算机科学交叉学科分支, 研究具有离散结构的优化问题解的性质和求解方法. 由于不同离散问题的结构差异, 出现了各种各样的研究手段和技巧. 针对组合优化的若干经典问题, 简述了算法和复杂性理论的研究进展.
|
| 关 键 词： | 组合优化 计算复杂性 近似算法 多面体组合 拟阵 |
New perspectives of several fundamental problems in combinatorial optimization |
| |
| CHEN Xujin,XU Dachuan,ZHANG Guochuan.New perspectives of several fundamental problems in combinatorial optimization[J].OR Transactions,2014,18(1):149-158. |
| |
| Authors: | CHEN Xujin XU Dachuan ZHANG Guochuan |
| |
| Institution: | 1. Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; 2. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China; 3. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China |
| |
| Abstract: | Combinatorial optimization, as an interdiscipline of operations research and computer science, has been developing since the mid-20th century. It characters optimization problems with discrete structures, and explores their solution methods. Due to the structural divergence in discrete problems, there has been a wide variety of methodologies and techniques. In this paper, we briefly introduce a number of fundamental problems in combinatorial optimization, and present the recent achievements together with some open problems. |
| |
| Keywords: | computational complexity approximation algorithms polyhedral combinatorics matriod |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
