|
|||||
|
|
| 一个约束乘积最大问题的强多项式时间算法 | |
| 引用本文： | 杨晓光,刘宏峰,汪光辉. 一个约束乘积最大问题的强多项式时间算法[J]. 系统科学与数学, 2005, 25(2): 196-203 |
| 作者姓名： | 杨晓光 刘宏峰 汪光辉 |
| 作者单位： | 1. 中国科学院数学与系统科学研究院系统科学研究所,北京,100080 2. 合肥工业大学理学院,合肥,230009 |
| 基金项目： | 国家自然科学基金(700221001,70425004)，国家973计划(2002CB312004)资助课题. |
| 摘 要： | 本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法. |
| 关 键 词： | 约束乘积最大问题 强多项式时间算法 |
| 修稿时间： | 2002-08-28 |
A STRONGLY POLYNOMIAL ALGORITHM FOR MAXIMIZATION OF PRODUCT UNDER BUDGET AND BOX CONSTRAINTS |
|
| Yang Xiaoguang,Liu Hongfeng,Wang Guanghui. A STRONGLY POLYNOMIAL ALGORITHM FOR MAXIMIZATION OF PRODUCT UNDER BUDGET AND BOX CONSTRAINTS[J]. Journal of Systems Science and Mathematical Sciences, 2005, 25(2): 196-203 | |
| Authors: | Yang Xiaoguang Liu Hongfeng Wang Guanghui |
| Affiliation: | (1)Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080;(2)Faculty of Science, Hefei University of Technology, Hefei 230009 |
| Abstract: | 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. |
| Keywords: | Maximizing product budget constraint box constraint strongly polynomial algorithm. |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 | |
| 点击此处可从《系统科学与数学》下载全文 | |