{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:35Z","timestamp":1740109295975,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T00:00:00Z","timestamp":1625184000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T00:00:00Z","timestamp":1625184000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"DFG","award":["TRR 154, Project A07"],"award-info":[{"award-number":["TRR 154, Project A07"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {APX}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>APX<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of these algorithms for problem instances arising in the context of real-world gas transport networks.<\/jats:p>","DOI":"10.1007\/s10107-021-01675-6","type":"journal-article","created":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T10:03:15Z","timestamp":1625220195000},"page":"361-386","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Packing under convex quadratic constraints"],"prefix":"10.1007","volume":"192","author":[{"given":"Max","family":"Klimm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0947-7193","authenticated-orcid":false,"given":"Marc E.","family":"Pfetsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rico","family":"Raber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,2]]},"reference":[{"issue":"3","key":"1675_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev, A.A., Sviridenko, M.I.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Combin. Optim. 8(3), 307\u2013328 (2004)","journal-title":"J. Combin. Optim."},{"key":"1675_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Hartline, J.D.: Knapsack auctions. In: Proceedings of the 17th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 1083\u20131092 (2006)","DOI":"10.1145\/1109557.1109677"},{"key":"1675_CR3","unstructured":"Bansal, N., Kimbrel, T., Pruhs, K.: Dynamic speed scaling to manage energy and temperature. In: Proceedings of the 45th Annual IEEE Symposium Foundations Computer Science. (FOCS), pp. 520\u2013529 (2004)"},{"key":"1675_CR4","doi-asserted-by":"publisher","DOI":"10.1142\/5273","volume-title":"Completely Positive Matrices","author":"A Berman","year":"2003","unstructured":"Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific Publishing, Singapore (2003)"},{"key":"1675_CR5","doi-asserted-by":"publisher","first-page":"1587","DOI":"10.1137\/090772988","volume":"40","author":"P Briest","year":"2011","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation techniques for utilitarian mechanism design. SIAM J. Comput. 40, 1587\u20131622 (2011)","journal-title":"SIAM J. Comput."},{"key":"1675_CR6","doi-asserted-by":"crossref","unstructured":"Chau, C.-K., Elbassioni, K.M., Khonji, M.: Truthful mechanisms for combinatorial allocation of electric power in alternating current electric systems for smart grid. ACM Trans. Econ. Comput., 5, Art.\u00a0nr.\u00a07, (2016)","DOI":"10.1145\/2955089"},{"key":"1675_CR7","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.dam.2017.06.020","volume":"230","author":"KM Elbassioni","year":"2017","unstructured":"Elbassioni, K.M., Nguyen, T.T.: Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions. Discrete Appl. Math. 230, 56\u201370 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1675_CR8","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/BFb0120892","volume":"12","author":"G Gallo","year":"1980","unstructured":"Gallo, G., Hammer, P.L., Simeone, B.: Quadratic knapsack problems. Math. Program. Study 12, 132\u2013149 (1980)","journal-title":"Math. Program. Study"},{"key":"1675_CR9","doi-asserted-by":"publisher","first-page":"587","DOI":"10.2307\/1914083","volume":"41","author":"A Gibbard","year":"1973","unstructured":"Gibbard, A.: Manipulation of voting schemes: a general result. Econometrica 41, 587\u2013601 (1973)","journal-title":"Econometrica"},{"issue":"1","key":"1675_CR10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"1675_CR11","doi-asserted-by":"crossref","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating $$k$$-dimensional matching. In S.\u00a0Arora, K.\u00a0Jansen, J.\u00a0D.\u00a0P. Rolim, and A.\u00a0Sahai (eds) Proceedings of the 7th International Workshop Approximation Algorithms for Combinatorial Optimization (APPROX), volume 2764 of Lecture Notes in Computer Science, pp. 83\u201397 (2003)","DOI":"10.1007\/978-3-540-45198-3_8"},{"key":"1675_CR12","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subsets problems. J. ACM 22, 463\u2013468 (1975)","journal-title":"J. ACM"},{"issue":"2","key":"1675_CR13","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/1067309.1067324","volume":"36","author":"S Irani","year":"2005","unstructured":"Irani, S., Pruhs, K.R.: Algorithmic problems in power management. SIGACT News 36(2), 63\u201376 (2005)","journal-title":"SIGACT News"},{"key":"1675_CR14","volume-title":"Complexity of Computer Computations, The IBM Research Symposia Series","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, The IBM Research Symposia Series. Springer, Boston, MA (1972)"},{"key":"1675_CR15","unstructured":"Klimm, M., Pfetsch, M.E., Raber, R., Skutella, M.: Packing under convex quadratic constraints. Preprint, TRR\u00a0154 (2019). https:\/\/opus4.kobv.de\/opus4-trr154\/frontdoor\/index\/index\/docId\/287"},{"key":"1675_CR16","unstructured":"Klimm, M., Pfetsch, M.E., Raber, R., Skutella, M.: On the robustness of potential-based flow networks. Preprint, TRR\u00a0154 (2020). https:\/\/opus4.kobv.de\/opus4-trr154\/frontdoor\/index\/index\/docId\/309"},{"key":"1675_CR17","doi-asserted-by":"crossref","unstructured":"Klimm, M., Pfetsch, M.E., Raber, R., Skutella, M.: Packing under convex quadratic constraints. In D.\u00a0Bienstock and G.\u00a0Zambelli (eds) Proceedings of the 21st International Conference on Integer Programming. and Combinatorial Optimization (IPCO), pp. 266\u2013279 (2020)","DOI":"10.1007\/978-3-030-45771-6_21"},{"issue":"5","key":"1675_CR18","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0041-5553(80)90098-1","volume":"20","author":"MK Kozlov","year":"1980","unstructured":"Kozlov, M.K., Tarasov, S.P., Khachiyan, L.G.: The polynomial solvability of convex quadratic programming. USSR Comput. Math. Math. Phys. 20(5), 223\u2013228 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"1675_CR19","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0176-2680(89)90049-9","volume":"5","author":"KA McCabe","year":"1989","unstructured":"McCabe, K.A., Rassenti, S.J., Smith, V.L.: Designing \u2018smart\u2019 computer-assisted markets: an experimental auction for gas networks. Eur. J. Polit. Econ. 5, 259\u2013283 (1989)","journal-title":"Eur. J. Polit. Econ."},{"key":"1675_CR20","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1016\/j.geb.2007.12.009","volume":"64","author":"A Mu\u2019alem","year":"2008","unstructured":"Mu\u2019alem, A., Nisan, N.: Truthful approximation mechanisms for restricted combinatorial auctions. Games Econ. Behav. 64, 612\u2013631 (2008)","journal-title":"Games Econ. Behav."},{"key":"1675_CR21","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1287\/moor.6.1.58","volume":"6","author":"RB Myerson","year":"1981","unstructured":"Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6, 58\u201373 (1981)","journal-title":"Math. Oper. Res."},{"key":"1675_CR22","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0957-1787(02)00038-3","volume":"11","author":"DM Newbery","year":"2002","unstructured":"Newbery, D.M.: Network capacity auctions: promise and problems. Util. Policy 11, 27\u201332 (2002)","journal-title":"Util. Policy"},{"key":"1675_CR23","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1287\/ijoc.2015.0678","volume":"28","author":"U Pferschy","year":"2016","unstructured":"Pferschy, U., Schauer, J.: Approximation of the quadratic knapsack problem. INFORMS J. Comput. 28, 308\u2013318 (2016)","journal-title":"INFORMS J. Comput."},{"key":"1675_CR24","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0167-6377(02)00122-0","volume":"30","author":"DJ Rader Jr","year":"2002","unstructured":"Rader, D.J., Jr., Woeginger, G.J.: The quadratic 0\u20131 knapsack problem with series-parallel support. Oper. Res. Lett. 30, 159\u2013166 (2002)","journal-title":"Oper. Res. Lett."},{"key":"1675_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01211118","volume":"4","author":"SJ Rassenti","year":"1994","unstructured":"Rassenti, S.J., Reynolds, S.S., Smit, V.L.: Cotenancy and competition in an experimental auction market for natural gas pipeline networks. Econ. Theory 4, 41\u201365 (1994)","journal-title":"Econ. Theory"},{"issue":"1","key":"1675_CR26","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/321864.321873","volume":"22","author":"S Sahni","year":"1975","unstructured":"Sahni, S.: Approximate algorithms for the $$0\/1$$ knapsack problem. J. ACM 22(1), 115\u2013124 (1975)","journal-title":"J. ACM"},{"key":"1675_CR27","doi-asserted-by":"crossref","unstructured":"Schmidt, M., A\u00dfmann, D., Burlacu, R., Humpola, J., Joormann, I., Kanelakis, N., Koch, T., Oucherif, D., Pfetsch, M.E., Schewe, L., Schwarz, R., Sirvent, M.: GasLib\u2014A Library of Gas Network Instances. Data, 2(4), article 40 (2017)","DOI":"10.3390\/data2040040"},{"key":"1675_CR28","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32, 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"1675_CR29","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1115\/1.4059982","volume":"34","author":"TR Weymouth","year":"1912","unstructured":"Weymouth, T.R.: Problems in natural gas engineering. Trans. Am. Soc. Mech. Eng. 34, 185\u2013231 (1912)","journal-title":"Trans. Am. Soc. Mech. Eng."},{"key":"1675_CR30","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1016\/j.peva.2012.07.002","volume":"69","author":"A Wierman","year":"2012","unstructured":"Wierman, A., Andrew, L.L.H., Tang, A.: Power-aware speed scaling in processor sharing systems: optimality and robustness. Perform. Eval. 69, 601\u2013622 (2012)","journal-title":"Perform. Eval."},{"key":"1675_CR31","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1287\/ijoc.12.1.57.11901","volume":"12","author":"GJ Woeginger","year":"2000","unstructured":"Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. 12, 57\u201374 (2000)","journal-title":"INFORMS J. Comput."},{"key":"1675_CR32","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Math. Oper. Res. 7, 410\u2013425 (1982)","journal-title":"Math. Oper. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01675-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01675-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01675-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T05:12:27Z","timestamp":1725340347000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01675-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,2]]},"references-count":32,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1675"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01675-6","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,7,2]]},"assertion":[{"value":"17 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}