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


An O(n) algorithm for quadratic knapsack problems
Authors:Peter Brucker
Institution:Fachbereich Mathematik, Universität Osnabrück, Postfach 4469, 4500 Osnabrück, Federal Republic of Germany
Abstract:An algorithm is presented which solves bounded quadratic optimization problems with n variables and one linear constraint in at most O(n) steps. The algorithm is based on a parametric approach combined with well-known ideas for constructing efficient algorithms. It improves an O(n log n) algorithm which has been developed for a more restricted case of the problem.
Keywords:nonlinear programming  convex programming  quadratic programming  knapsack problem  parametric programming
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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