| 广义二分搜索及其在 LP 多项式算法复杂度证明中的应用 |
| |
| 引用本文： | 章祥荪,堵丁柱. 广义二分搜索及其在 LP 多项式算法复杂度证明中的应用[J]. 系统科学与数学, 1990, 10(4): 371-376 |
| |
| 作者姓名： | 章祥荪 堵丁柱 |
| |
| 作者单位： | 中国科学院应用数学研究所(章祥荪)，中国科学院应用数学研究所(堵丁柱) |
| |
| 摘 要： | Khachiyan 和 Karmarkar 方法的提出,不仅解决了长期悬而未决的线性规划(LP)问题的多项式时间算法的存在性问题,而且开辟了优化算法设计上新的方法论体系.目前的兴趣之一是把这一方法论体系应用到一般的连续优化问题中去.一个组合优化问题,同一般优化问题一样,可以表达成一个二元组((?),c),其中(?)是可行解集合,c 是定义在(?)上的实目标函数.对于组合问题,一般地,(?)是离
|
EXTENDED BINARY SEARCH AND ITS APPLCATION IN DESIGN OF POLYNOMIAL-TIME ALGORITHM FOR LP |
| |
| ZHANG XIANG-SUN DU DING-ZHU. EXTENDED BINARY SEARCH AND ITS APPLCATION IN DESIGN OF POLYNOMIAL-TIME ALGORITHM FOR LP[J]. Journal of Systems Science and Mathematical Sciences, 1990, 10(4): 371-376 |
| |
| Authors: | ZHANG XIANG-SUN DU DING-ZHU |
| |
| Affiliation: | Institute of Applied Mathematics,Academia Sinica |
| |
| Abstract: | This paper presents an unified methodology for design of polynomial-time algorithms forLP by summarizing Khachiyan's algorithm and Karmarkar's algorithm.The authors deve-loped the concepts of binary search are developel into the so-called extended binary search,whi-ch is used as an unified model to analyze the complexities of algorthms and to help designnew algorithms. |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
|
点击此处可从《系统科学与数学》下载全文 |
