首页 | 本学科首页   官方微博 | 高级检索  
     检索      

一个约束乘积最大问题的强多项式时间算法
引用本文:杨晓光,刘宏峰,汪光辉.一个约束乘积最大问题的强多项式时间算法[J].系统科学与数学,2005,25(2):196-203.
作者姓名:杨晓光  刘宏峰  汪光辉
作者单位:1. 中国科学院数学与系统科学研究院系统科学研究所,北京,100080
2. 合肥工业大学理学院,合肥,230009
基金项目:国家自然科学基金(700221001,70425004),国家973计划(2002CB312004)资助课题.
摘    要:本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.

关 键 词:约束乘积最大问题  强多项式时间算法
修稿时间:2002年8月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
Institution:(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 万方数据 等数据库收录!
点击此处可从《系统科学与数学》浏览原始摘要信息
点击此处可从《系统科学与数学》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号