{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:46:18Z","timestamp":1740123978135,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T00:00:00Z","timestamp":1723420800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T00:00:00Z","timestamp":1723420800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-20-1-2156"],"award-info":[{"award-number":["N00014-20-1-2156"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016464","name":"School of Public and International Affairs, Virginia Polytechnic Institute and State University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100016464","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study continuous, equality knapsack problems with uniform separable, non-convex objective functions that are continuous, antisymmetric about a point, and have concave and convex regions. For example, this model captures a simple allocation problem with the goal of optimizing an expected value where the objective is a sum of cumulative distribution functions of identically distributed normal distributions (i.e., a sum of inverse probit functions). We prove structural results of this model under general assumptions and provide two algorithms for efficient optimization: (1) running in linear time and (2) running in a constant number of operations given preprocessing of the objective function.<\/jats:p>","DOI":"10.1007\/s10957-024-02503-5","type":"journal-article","created":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T09:02:53Z","timestamp":1723453373000},"page":"1060-1076","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Continuous Equality Knapsack with Probit-Style Objectives"],"prefix":"10.1007","volume":"202","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4428-0396","authenticated-orcid":false,"given":"Jamie","family":"Fravel","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2730-0084","authenticated-orcid":false,"given":"Robert","family":"Hildebrand","sequence":"additional","affiliation":[]},{"given":"Laurel","family":"Travis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,12]]},"reference":[{"issue":"2","key":"2503_CR1","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.ejor.2007.10.060","volume":"193","author":"S A\u011fral\u0131","year":"2009","unstructured":"A\u011fral\u0131, S., Geunes, J.: Solving knapsack problems with S-curve return functions. Eur. J. Oper. Res. 193(2), 605\u2013615 (2009). https:\/\/doi.org\/10.1016\/j.ejor.2007.10.060","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"2503_CR2","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1287\/mnsc.27.4.431","volume":"27","author":"GR Bitran","year":"1981","unstructured":"Bitran, G.R., Hax, A.C.: Disaggregation and resource allocation using convex knapsack problems with bounded variables. Manag. Sci. 27(4), 431\u2013441 (1981). https:\/\/doi.org\/10.1287\/mnsc.27.4.431","journal-title":"Manag. Sci."},{"issue":"5","key":"2503_CR3","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1016\/S0305-0548(00)00089-7","volume":"29","author":"KM Bretthauer","year":"2002","unstructured":"Bretthauer, K.M., Shetty, B.: A pegging algorithm for the nonlinear resource allocation problem. Comput. Oper. Res. 29(5), 505\u2013527 (2002). https:\/\/doi.org\/10.1016\/S0305-0548(00)00089-7","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"2503_CR4","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1287\/opre.43.4.670","volume":"43","author":"KM Bretthauer","year":"1995","unstructured":"Bretthauer, K.M., Shetty, B.: The nonlinear resource allocation problem. Oper. Res. 43(4), 670\u2013683 (1995). https:\/\/doi.org\/10.1287\/opre.43.4.670","journal-title":"Oper. Res."},{"issue":"4","key":"2503_CR5","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1287\/mnsc.5.4.453","volume":"5","author":"C Derman","year":"1959","unstructured":"Derman, C.: A simple allocation problem. Manag. Sci. 5(4), 453\u2013459 (1959). https:\/\/doi.org\/10.1287\/mnsc.5.4.453","journal-title":"Manag. Sci."},{"key":"2503_CR6","unstructured":"Fravel, J., et al.: Optimizing representation in redistricting: dual bounds for partitioning problems with non-convex objectives (2023). arXiv:2305.17298"},{"issue":"11","key":"2503_CR7","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1057\/jors.1980.186","volume":"31","author":"JR Freeland","year":"1980","unstructured":"Freeland, J.R., Weinberg, C.B.: S-shaped response functions: implications for decision models. J. Oper. Res. Soc. 31(11), 1001\u20131007 (1980). https:\/\/doi.org\/10.1057\/jors.1980.186","journal-title":"J. Oper. Res. Soc."},{"key":"2503_CR8","doi-asserted-by":"publisher","DOI":"10.1111\/lsq.12448","author":"N Goedert","year":"2024","unstructured":"Goedert, N., et al.: Asymmetries in potential for partisan gerrymandering. Legis. Stud. Q. (2024). https:\/\/doi.org\/10.1111\/lsq.12448","journal-title":"Legis. Stud. Q."},{"key":"2503_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/21565503.2024.2331723","volume":"1","author":"N Goedert","year":"2024","unstructured":"Goedert, N., et al.: Black representation and district compactness in Southern congressional districts. Polit. Groups Identit. 1, 1 (2024). https:\/\/doi.org\/10.1080\/21565503.2024.2331723","journal-title":"Polit. Groups Identit."},{"issue":"2","key":"2503_CR10","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s10666-007-9088-4","volume":"13","author":"RG Haight","year":"2007","unstructured":"Haight, R.G., Travis, L.E.: Reserve design to maximize species persistence. Environ. Model. Assess. 13(2), 243\u2013253 (2007). https:\/\/doi.org\/10.1007\/s10666-007-9088-4","journal-title":"Environ. Model. Assess."},{"issue":"3","key":"2503_CR11","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0167-6377(95)00009-9","volume":"17","author":"DS Hochbaum","year":"1995","unstructured":"Hochbaum, D.S.: A nonlinear Knapsack problem. Oper. Res. Lett. 17(3), 103\u2013110 (1995). https:\/\/doi.org\/10.1016\/0167-6377(95)00009-9","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"2503_CR12","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1287\/opre.46.2.272","volume":"46","author":"MS Kodialam","year":"1998","unstructured":"Kodialam, M.S., Luss, H.: Algorithms for separable nonlinear resource allocation problems. Oper. Res. 46(2), 272\u2013284 (1998). https:\/\/doi.org\/10.1287\/opre.46.2.272","journal-title":"Oper. Res."},{"issue":"1","key":"2503_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2006.12.006","volume":"185","author":"M Patriksson","year":"2008","unstructured":"Patriksson, M.: A survey on the continuous nonlinear resource allocation problem. Eur. J. Oper. Res. 185(1), 1\u201346 (2008). https:\/\/doi.org\/10.1016\/j.ejor.2006.12.006","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"2503_CR14","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.ejor.2015.01.029","journal-title":"Eur. J. Oper. Res."},{"issue":"7","key":"2503_CR15","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1287\/mnsc.15.7.362","volume":"15","author":"MH Rothkopf","year":"1969","unstructured":"Rothkopf, M.H.: A model of rational competitive bidding. Manag. Sci. 15(7), 362\u2013373 (1969). https:\/\/doi.org\/10.1287\/mnsc.15.7.362","journal-title":"Manag. Sci."},{"issue":"2","key":"2503_CR16","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1016\/j.ejor.2013.12.035","volume":"236","author":"V Srivastava","year":"2014","unstructured":"Srivastava, V., Bullo, F.: Knapsack problems with sigmoid utilities: approximation algorithms via hybrid optimization. Eur. J. Oper. Res. 236(2), 488\u2013498 (2014). https:\/\/doi.org\/10.1016\/j.ejor.2013.12.035","journal-title":"Eur. J. Oper. Res."},{"key":"2503_CR17","doi-asserted-by":"publisher","DOI":"10.1155\/2013\/513918","author":"L Zhang","year":"2013","unstructured":"Zhang, L.: A Newton-type algorithm for solving problems of search theory. Adv. Oper. Res. (2013). https:\/\/doi.org\/10.1155\/2013\/513918","journal-title":"Adv. Oper. Res."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-024-02503-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-024-02503-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-024-02503-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:06:04Z","timestamp":1725458764000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-024-02503-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,12]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["2503"],"URL":"https:\/\/doi.org\/10.1007\/s10957-024-02503-5","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2024,8,12]]},"assertion":[{"value":"2 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}