{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T16:59:46Z","timestamp":1743094786075,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030457709"},{"type":"electronic","value":"9783030457716"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-45771-6_21","type":"book-chapter","created":{"date-parts":[[2020,4,13]],"date-time":"2020-04-13T21:03:32Z","timestamp":1586811812000},"page":"266-279","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","author":[{"given":"Max","family":"Klimm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[[2020,4,14]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Hartline, J.D.: Knapsack auctions. In: Proceedings of 17th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 1083\u20131092 (2006)","key":"21_CR1","DOI":"10.1145\/1109557.1109677"},{"unstructured":"Bansal, N., Kimbrel, T., Pruhs, K.: Dynamic speed scaling to manage energy and temperature. In: Proceedings of 45th Annual IEEE Symposium Foundations Computer Science (FOCS), pp. 520\u2013529 (2004)","key":"21_CR2"},{"doi-asserted-by":"crossref","unstructured":"Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific Publishing, Singapore (2003)","key":"21_CR3","DOI":"10.1142\/5273"},{"key":"21_CR4","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."},{"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 (2016). Art. nr. 7","key":"21_CR5"},{"key":"21_CR6","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":"21_CR7","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":"21_CR8","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":"21_CR9","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 Mathematica 182(1), 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"doi-asserted-by":"crossref","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subsets problems. J. ACM 22, 463\u2013468 (1975)","key":"21_CR10","DOI":"10.1145\/321906.321909"},{"issue":"2","key":"21_CR11","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"},{"doi-asserted-by":"publisher","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 (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","key":"21_CR12","DOI":"10.1007\/978-1-4684-2001-2_9"},{"unstructured":"Klimm, M., Pfetsch, M.E., Raber, R., Skutella, M.: Packing under convex quadratic constraints. Preprint (2019). arXiv:1912.00468 [math.OC]","key":"21_CR13"},{"unstructured":"Klimm, M., Pfetsch, M.E., Raber, R., Skutella, M.: On the robustness of potential-based flow networks. Preprint (2020). https:\/\/opus4.kobv.de\/opus4-trr154\/frontdoor\/index\/index\/docId\/309","key":"21_CR14"},{"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)","key":"21_CR15"},{"key":"21_CR16","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":"21_CR17","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":"21_CR18","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."},{"doi-asserted-by":"crossref","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming, vol. 13. SIAM (1994)","key":"21_CR19","DOI":"10.1137\/1.9781611970791"},{"key":"21_CR20","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. Utilities Policy 11, 27\u201332 (2002)","journal-title":"Utilities Policy"},{"key":"21_CR21","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."},{"unstructured":"Rader Jr., D.J., Woeginger, G.J.: The quadratic 0\u20131 knapsack problem with series-parallel support. Oper. Res. Lett. 30, 159\u2013166 (2002)","key":"21_CR22"},{"key":"21_CR23","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":"21_CR24","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"},{"doi-asserted-by":"crossref","unstructured":"Schmidt, M., et al.: GasLib - a library of gas network instances. Data 2(4) (2017). Article 40","key":"21_CR25","DOI":"10.3390\/data2040040"},{"key":"21_CR26","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":"21_CR27","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."},{"doi-asserted-by":"crossref","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)","key":"21_CR28","DOI":"10.1016\/j.peva.2012.07.002"},{"key":"21_CR29","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."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45771-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T22:44:31Z","timestamp":1722725071000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45771-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030457709","9783030457716"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45771-6_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"14 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"London","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.xixilogic.org\/events\/clar2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"126","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}