摘要
Khachiyan 和 Karmarkar 方法的提出,不仅解决了长期悬而未决的线性规划(LP)问题的多项式时间算法的存在性问题,而且开辟了优化算法设计上新的方法论体系.目前的兴趣之一是把这一方法论体系应用到一般的连续优化问题中去.一个组合优化问题,同一般优化问题一样,可以表达成一个二元组((?),c),其中(?)是可行解集合,c 是定义在(?)上的实目标函数.对于组合问题,一般地,(?)
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.
出处
《系统科学与数学》
CSCD
北大核心
1990年第4期371-376,共6页
Journal of Systems Science and Mathematical Sciences
