Abstract
We give a linear time algorithm for the continuous quadratic knapsack problem which is simpler than existing methods and competitive in practice. Encouraging computational results are presented for large-scale problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Brucker, P.: An O(n) algorithm for quadratic knapsack problems. Oper. Res. Lett. 3, 163–166 (1984)
Calamai, P.H., Moré, J.J.: Quasi-Newton updates with bounds. SIAM J. Numer. Anal. 24, 1434–1441 (1987)
Maculan, N., Santiago, C.P., Macambira, E.M., Jardim, M.H.C.: An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in R n. J. Optim. Theory Appl. 117, 553–574 (2003)
Pardalos, P.M., Kovoor, N.: An algorithm for a singly-constrained class of quadratic programs subject to upper and lower bounds. Math. Program. 46, 321–328 (1990)
Bretthauer, K.M., Shetty, B., Syam, S.: A branch- and bound-algorithm for integer quadratic knapsack problems. ORSA J. Comput. 7, 109–116 (1995)
Knuth, D.E.: Sorting and Searching, 2nd edn. The Art of Computer Programming, vol. III. Addison–Wesley, Reading (1998)
Kiwiel, K.C.: On Floyd and Rivest’s select algorithm. Theor. Comput. Sci. 347, 214–238 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by J.P. Crouzeix.
The author thanks the Associate Editor and an anonymous referee for their helpful comments.
Rights and permissions
About this article
Cite this article
Kiwiel, K.C. On Linear-Time Algorithms for the Continuous Quadratic Knapsack Problem. J Optim Theory Appl 134, 549–554 (2007). https://doi.org/10.1007/s10957-007-9259-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-007-9259-0