{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T22:40:47Z","timestamp":1779230447250,"version":"3.51.4"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2016,11,5]],"date-time":"2016-11-05T00:00:00Z","timestamp":1478304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s10107-016-1082-7","type":"journal-article","created":{"date-parts":[[2016,11,5]],"date-time":"2016-11-05T01:26:02Z","timestamp":1478309162000},"page":"193-227","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time"],"prefix":"10.1007","volume":"164","author":[{"given":"Chanaka","family":"Edirisinghe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaehwan","family":"Jeong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,5]]},"reference":[{"key":"1082_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/9780471703778","volume-title":"Linear Programming and Network Flows","author":"MS Bazaraa","year":"2009","unstructured":"Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows, 4th edn. Wiley, New York (2009)","edition":"4"},{"key":"1082_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/0471787779","volume-title":"Nonlinear Programming: Theory and Applications","author":"MS Bazaraa","year":"2006","unstructured":"Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Applications, 3rd edn. Wiley, New York (2006)","edition":"3"},{"issue":"1","key":"1082_CR3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s12532-011-0033-9","volume":"4","author":"J Chen","year":"2012","unstructured":"Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4(1), 33\u201352 (2012)","journal-title":"Math. Program. Comput."},{"issue":"2","key":"1082_CR4","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/s12532-014-0066-y","volume":"6","author":"R Cominetti","year":"2014","unstructured":"Cominetti, R., Mascarenhas, W., Silva, P.: A Newton\u2019s method for the continuous quadratic knapsack problem. Math. Program. Comput. 6(2), 151\u2013169 (2014)","journal-title":"Math. Program. Comput."},{"issue":"3","key":"1082_CR5","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/s10107-005-0595-2","volume":"106","author":"YH Dai","year":"2006","unstructured":"Dai, Y.H., Fletcher, R.: New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math. Program. 106(3), 403\u2013421 (2006)","journal-title":"Math. Program."},{"issue":"1","key":"1082_CR6","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s10107-015-0918-x","volume":"158","author":"C Edirisinghe","year":"2016","unstructured":"Edirisinghe, C., Jeong, J.: An efficient global algorithm for a class of indefinite separable quadratic programs. Math. Program. 158(1), 143\u2013173 (2016)","journal-title":"Math. Program."},{"issue":"3","key":"1082_CR7","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1145\/360680.360694","volume":"18","author":"RW Floyd","year":"1975","unstructured":"Floyd, R.W., Rivest, R.L.: Algorithm 489: the algorithm select for finding the i th smallest of n elements. Commun. ACM 18(3), 173 (1975)","journal-title":"Commun. ACM"},{"issue":"3","key":"1082_CR8","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","volume":"45","author":"S Martello","year":"1999","unstructured":"Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0\u20131 knapsack problem. Manag. Sci. 45(3), 414\u2013424 (1999)","journal-title":"Manag. Sci."},{"issue":"1","key":"1082_CR9","first-page":"397","volume":"49","author":"JJ Mor\u00e9","year":"1991","unstructured":"Mor\u00e9, J.J., Vavasis, S.A.: On the solution of concave knapsack problems. Math. Program. 49(1), 397\u2013411 (1991)","journal-title":"Math. Program."},{"issue":"3","key":"1082_CR10","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1287\/mnsc.2013.1772","volume":"60","author":"Y Nakagawa","year":"2014","unstructured":"Nakagawa, Y., James, R.J.W., Rego, C., Edirisinghe, C.: Entropy-based optimization of nonlinear separable discrete decision models. Manag. Sci. 60(3), 695\u2013707 (2014)","journal-title":"Manag. Sci."},{"issue":"3","key":"1082_CR11","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1016\/j.ejor.2015.01.029","volume":"243","author":"M Patriksson","year":"2015","unstructured":"Patriksson, M., Str\u00f6mberg, C.: Algorithms for the continuous nonlinear resource allocation problem\u2014new implementations and numerical studies. Eur. J. Oper. Res. 243(3), 703\u2013722 (2015)","journal-title":"Eur. J. Oper. Res."},{"issue":"9","key":"1082_CR12","doi-asserted-by":"crossref","first-page":"2271","DOI":"10.1016\/j.cor.2004.03.002","volume":"32","author":"D Pisinger","year":"2005","unstructured":"Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32(9), 2271\u20132284 (2005)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"1082_CR13","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01581193","volume":"55","author":"AG Robinson","year":"1992","unstructured":"Robinson, A.G., Jiang, N., Lerme, C.S.: On the continuous quadratic knapsack-problem. Math. Program. 55(1), 99\u2013108 (1992)","journal-title":"Math. Program."},{"issue":"2","key":"1082_CR14","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01586048","volume":"54","author":"SA Vavasis","year":"1992","unstructured":"Vavasis, S.A.: Local minima for indefinite quadratic knapsack-problems. Math. Program. 54(2), 127\u2013153 (1992)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-1082-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1082-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1082-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,9]],"date-time":"2017-06-09T03:10:44Z","timestamp":1496977844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-1082-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,5]]},"references-count":14,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["1082"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-1082-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,5]]}}}