{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:49:21Z","timestamp":1763459361811,"version":"3.45.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,5,10]],"date-time":"2017-05-10T00:00:00Z","timestamp":1494374400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Project Agency","doi-asserted-by":"crossref","award":["HR0011-12-C-0011"],"award-info":[{"award-number":["HR0011-12-C-0011"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"crossref","award":["N00014-11-1-0068, N00014-15-1-2048"],"award-info":[{"award-number":["N00014-11-1-0068, N00014-15-1-2048"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["0620286, 1522629"],"award-info":[{"award-number":["0620286, 1522629"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:p>This article considers the problem of minimizing a convex, separable quadratic function subject to a knapsack constraint and a box constraint. An algorithm called NAPHEAP has been developed to solve this problem. The algorithm solves the Karush-Kuhn-Tucker system using a starting guess to the optimal Lagrange multiplier and updating the guess monotonically in the direction of the solution. The starting guess is computed using the variable fixing method or is supplied by the user. A key innovation in our algorithm is the implementation of a heap data structure for storing the break points of the dual function and computing the solution of the dual problem. Also, a new version of the variable fixing algorithm is developed that is convergent even when the objective Hessian is not strictly positive definite. The hybrid algorithm NAPHEAP that uses a Newton-type method (variable fixing method, secant method, or Newton's method) to bracket a root, followed by a heap-based monotone break point search, can be faster than a Newton-type method by itself, as demonstrated in the numerical experiments.<\/jats:p>","DOI":"10.1145\/2828635","type":"journal-article","created":{"date-parts":[[2016,5,11]],"date-time":"2016-05-11T08:11:38Z","timestamp":1462954298000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["An Efficient Hybrid Algorithm for the Separable Convex Quadratic Knapsack Problem"],"prefix":"10.1145","volume":"42","author":[{"given":"Timothy A.","family":"Davis","sequence":"first","affiliation":[{"name":"Texas A&amp;M University, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William W.","family":"Hager","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James T.","family":"Hungerford","sequence":"additional","affiliation":[{"name":"M.A.I.O.R., Lucca, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,5,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.4.431"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00039-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1996.44"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(84)90010-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0724092"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1975-0367131-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-014-0066-y"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms. MIT Press Cambridge MA.","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.1.94"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0595-2"},{"volume-title":"The Theory of Max-Min and its Applications to Weapons Allocation Problems","author":"Danskin J. M.","key":"e_1_2_1_11_1","unstructured":"J. M. Danskin. 1967. The Theory of Max-Min and its Applications to Weapons Allocation Problems. Springer-Verlag, New York, NY."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595910002594"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0644-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.05.042"},{"key":"e_1_2_1_15_1","unstructured":"W. W. Hager J. T. Hungerford and I. Safro. 2014. A multilevel bilinear programming algorithm for the vertex separator problem. http:\/\/clas.ufl.edu\/users\/hager\/papers\/GP\/ml.pdf."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199335829"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/050635225"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588328"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/216227.216233"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-007-9317-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","unstructured":"D. G. Luenberger and Y. Ye. 2008. Linear and Nonlinear Programming. Springer Berlin.","DOI":"10.5555\/2843008"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023997605430"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/9668.9680"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.2.166"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585748"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113611.3113961"},{"volume-title":"Convex Analysis","author":"Rockafellar R. T.","key":"e_1_2_1_27_1","unstructured":"R. T. Rockafellar. 1970. Convex Analysis. Princeton University Press, Princeton, NJ."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1990.121"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3585"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210407"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2828635","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2828635","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2828635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:44:01Z","timestamp":1763459041000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2828635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,10]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2828635"],"URL":"https:\/\/doi.org\/10.1145\/2828635","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2016,5,10]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}