An O(n) algorithm for quadratic knapsack problems |
| |
Authors: | Peter Brucker |
| |
Affiliation: | 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 等数据库收录! |