一个约束乘积最大问题的强多项式时间算法  

A STRONGLY POLYNOMIAL ALGORITHM FOR MAXIMIZATION OF PRODUCT UNDER BUDGET AND BOX CONSTRAINTS

作　　者：杨晓光[1] 刘宏峰[1] 汪光辉[2] 

机构地区：[1]中国科学院数学与系统科学研究院系统科学研究所,北京100080 [2]合肥工业大学理学院,合肥230009

出　　处：《系统科学与数学》2005年第2期196-203,共8页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(700221001;70425004);国家973计划(2002CB312004)资助课题.

摘　　要：本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.In this paper, we consider the following maximization problem of product under budget and box constraints We present a strongly polynomial algorithm which runs in O(n2) times for the problem. For the problem only with one-side bound constraint, we further propose a strongly polynomial algorithm running in O(nlnn) times.

关 键 词：多项式时间算法 乘积 结构特征 计算时间 单边约束 最优解 复杂度 

分 类 号：O241[理学—计算数学]