广义二分搜索及其在 LP 多项式算法复杂度证明中的应用

Khachiyan 和 Karmarkar 方法的提出,不仅解决了长期悬而未决的线性规划(LP)问题的多项式时间算法的存在性问题,而且开辟了优化算法设计上新的方法论体系.目前的兴趣之一是把这一方法论体系应用到一般的连续优化问题中去.一个组合优化问题,同一般优化问题一样,可以表达成一个二元组((?),c),其中(?)是可行解集合,c 是定义在(?)上的实目标函数.对于组合问题,一般地,(?)是离

EXTENDED BINARY SEARCH AND ITS APPLCATION IN DESIGN OF POLYNOMIAL-TIME ALGORITHM FOR LP

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.