摘要
本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为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.
出处
《系统科学与数学》
CSCD
北大核心
2005年第2期196-203,共8页
Journal of Systems Science and Mathematical Sciences
基金
国家自然科学基金(700221001
70425004)
国家973计划(2002CB312004)资助课题.