{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T04:51:38Z","timestamp":1749185498214,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031710322"},{"type":"electronic","value":"9783031710339"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-71033-9_27","type":"book-chapter","created":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T00:02:17Z","timestamp":1725321737000},"page":"483-500","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["k-Times Bin Packing and\u00a0its Application to\u00a0Fair Electricity Distribution"],"prefix":"10.1007","author":[{"given":"Dinesh Kumar","family":"Baghel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Ravsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erel","family":"Segal-Halevi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,31]]},"reference":[{"key":"27_CR1","unstructured":"Baghel, D.K., Ravsky, A., Segal-Halevi, E.: $$k$$-times bin packing and its application to fair electricity distribution (2024). arXiv:2311.16742"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Baker, B.S.: A new proof for the first-fit decreasing bin-packing algorithm. J. Algorithms 6(1), 49\u201370 (1985). https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677485900185","DOI":"10.1016\/0196-6774(85)90018-5"},{"key":"27_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598975","volume-title":"Fair Division: From Cake-Cutting to Dispute Resolution","author":"SJ Brams","year":"1996","unstructured":"Brams, S.J., Taylor, A.D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996). https:\/\/doi.org\/10.1017\/CBO9780511598975"},{"key":"27_CR4","unstructured":"Doron-Arad, I., Kulik, A., Shachnai, H.: Bin packing with partition matroid can be approximated within $$o({OPT})$$ bins (arXiv:2212.01025) (2022). http:\/\/arxiv.org\/abs\/2212.01025, arXiv:2212.01025 [cs]"},{"key":"27_CR5","doi-asserted-by":"publisher","unstructured":"Dosa, G., Sgall, J.: First Fit bin packing: a tight analysis. In: Leibniz International Proceedings in Informatics, LIPIcs, vol. 20, pp. 538\u2013549 (2013). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2013.538, iSBN: 9783939897507","DOI":"10.4230\/LIPIcs.STACS.2013.538"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"D\u00f3sa, G.: The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is F F D ( I ) $$\\le $$ 11 \/ 9 OP T ( I ) + 6 \/ 9 2007(2), 1\u201311 (2007)","DOI":"10.1007\/978-3-540-74450-4_1"},{"issue":"11101065","key":"27_CR7","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2013.09.007","volume":"510","author":"G D\u00f3sa","year":"2013","unstructured":"D\u00f3sa, G., Li, R., Han, X., Tuza, Z.: Tight absolute bound for first fit decreasing bin-packing: FFD(L) $$\\le $$ 11\/9OPT(L) + 6\/9. Theoret. Comput. Sci. 510(11101065), 13\u201361 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2013.09.007","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR8","doi-asserted-by":"publisher","unstructured":"Garey, M.R., Graham, R.L., Ullman, J.D.: Worst-case analysis of memory allocation algorithms. In: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, pp. 143\u2013150. STOC \u201972, Association for Computing Machinery, New York, NY, USA (1972). https:\/\/doi.org\/10.1145\/800152.804907","DOI":"10.1145\/800152.804907"},{"key":"27_CR9","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1990)"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Garey, M., Graham, R., Johnson, D., Yao, A.C.C.: Resource constrained scheduling as generalized bin packing. J. Comb. Theory, Ser. A 21(3), 257\u2013298 (1976). https:\/\/www.sciencedirect.com\/science\/article\/pii\/0097316576900017","DOI":"10.1016\/0097-3165(76)90001-7"},{"issue":"3","key":"27_CR11","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/S0305-0548(02)00195-8","volume":"31","author":"M Gendreau","year":"2004","unstructured":"Gendreau, M., Laporte, G., Semet, F.: Heuristics and lower bounds for the bin packing problem with conflicts. Comput. Oper. Res. 31(3), 347\u2013358 (2004). https:\/\/doi.org\/10.1016\/S0305-0548(02)00195-8","journal-title":"Comput. Oper. Res."},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981). http:\/\/link.springer.com\/10.1007\/BF02579273","DOI":"10.1007\/BF02579273"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Hoberg, R., Rothvoss, T.: A logarithmic additive integrality gap for bin packing. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2616\u20132625. Society for Industrial and Applied Mathematics (2017). http:\/\/epubs.siam.org\/doi\/10.1137\/1.9781611974782.172","DOI":"10.1137\/1.9781611974782.172"},{"key":"27_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BFb0054353","volume-title":"Algorithm Theory \u2014 SWAT\u201998","author":"K Jansen","year":"1998","unstructured":"Jansen, K.: An approximation scheme for bin packing with conflicts. In: Arnborg, S., Ivansson, L. (eds.) SWAT 1998. LNCS, vol. 1432, pp. 35\u201346. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0054353"},{"key":"27_CR15","unstructured":"Johnson, D.S.: Near-Optimal Bin Packing Algorithms. Thesis, p. 400 (1973)"},{"key":"27_CR16","doi-asserted-by":"publisher","unstructured":"Karmarkar, N., Karp, R.M.: Efficient approximation scheme for the one-dimensional bin-packing problem. In: Annual Symposium on Foundations of Computer Science - Proceedings, pp. 312\u2013320 (1982). https:\/\/doi.org\/10.1109\/sfcs.1982.61","DOI":"10.1109\/sfcs.1982.61"},{"issue":"2","key":"27_CR17","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1016\/j.rser.2011.11.013","volume":"16","author":"K Kaygusuz","year":"2012","unstructured":"Kaygusuz, K.: Energy for sustainable development: a case of developing countries. Renew. Sustain. Energy Rev. 16(2), 1116\u20131126 (2012). https:\/\/doi.org\/10.1016\/j.rser.2011.11.013","journal-title":"Renew. Sustain. Energy Rev."},{"issue":"15","key":"27_CR18","doi-asserted-by":"publisher","first-page":"1262","DOI":"10.1007\/BF02882754","volume":"42","author":"R Li","year":"1997","unstructured":"Li, R., Yue, M.: The proof of FFD(L) $$<$$ -OPT(L) + 7\/9. Chin. Sci. Bull. 42(15), 1262\u20131265 (1997). https:\/\/doi.org\/10.1007\/BF02882754","journal-title":"Chin. Sci. Bull."},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Oluwasuji, O.I., Malik, O., Zhang, J., Ramchurn, S.D.: Algorithms for fair load shedding in developing countries. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pp. 1590\u20131596. International Joint Conferences on Artificial Intelligence Organization, Stockholm, Sweden (2018). https:\/\/www.ijcai.org\/proceedings\/2018\/220","DOI":"10.24963\/ijcai.2018\/220"},{"key":"27_CR20","doi-asserted-by":"crossref","unstructured":"Oluwasuji, O.I., Malik, O., Zhang, J., Ramchurn, S.D.: Solving the fair electric load shedding problem in developing countries. Auton. Agents Multi-Agent Syst. 34(1), 12 (2020). http:\/\/link.springer.com\/10.1007\/s10458-019-09428-8","DOI":"10.1007\/s10458-019-09428-8"},{"key":"27_CR21","doi-asserted-by":"crossref","unstructured":"Rothvoss, T.: Approximating bin packing within O(log opt $$\\cdot $$ log log opt) bins. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 20\u201329. IEEE, Berkeley, CA, USA (Oct 2013). https:\/\/ieeexplore.ieee.org\/document\/6686137\/","DOI":"10.1109\/FOCS.2013.11"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Steinhaus, H.: Sur la division pragmatique. Econometrica 17, 315\u2013319 (1949). http:\/\/www.jstor.org\/stable\/1907319","DOI":"10.2307\/1907319"},{"key":"27_CR23","unstructured":"Ullman, J.D.: The Performance of a Memory Allocation Algorithm. Technical report (Princeton University. Department of Electrical Engineering. Computer Sciences Laboratory), Princeton University (1971). https:\/\/books.google.co.il\/books?id=gnwNPwAACAAJ"},{"key":"27_CR24","doi-asserted-by":"publisher","unstructured":"Fernandez de\u00a0la Vega, W., Lueker, G.S.: Bin packing can be solved within 1 + $$\\epsilon $$ in linear time. Combinatorica 1(4), 349\u2013355 (1981). https:\/\/doi.org\/10.1007\/BF02579456","DOI":"10.1007\/BF02579456"},{"key":"27_CR25","doi-asserted-by":"publisher","unstructured":"Webb, Jack\u00a0Robertson, W.: Cake-Cutting Algorithms: Be Fair if You Can. A K Peters\/CRC Press, New York (1998). https:\/\/doi.org\/10.1201\/9781439863855","DOI":"10.1201\/9781439863855"},{"key":"27_CR26","unstructured":"Wikipedia contributors: Configuration linear program \u2014 Wikipedia, the free encyclopedia (2023). https:\/\/en.wikipedia.org\/w\/index.php?title=Configuration_linear_program&oldid=1139054649. Accessed 16 March 2023"},{"issue":"15","key":"27_CR27","doi-asserted-by":"publisher","first-page":"1668","DOI":"10.1016\/j.dam.2010.05.026","volume":"158","author":"B Xia","year":"2010","unstructured":"Xia, B., Tan, Z.: Tighter bounds of the first fit algorithm for the bin-packing problem. Discr. Appl. Math. 158(15), 1668\u20131675 (2010). https:\/\/doi.org\/10.1016\/j.dam.2010.05.026","journal-title":"Discr. Appl. Math."},{"issue":"4","key":"27_CR28","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02009683","volume":"7","author":"M Yue","year":"1991","unstructured":"Yue, M.: A simple proof of the inequality FFD(l) $$\\le $$ 11\/9OPT(L)+ 1,$$\\forall $$ L for the FFD bin-packing algorithm. Acta Math. Appl. Sin. 7(4), 321\u2013331 (1991)","journal-title":"Acta Math. Appl. Sin."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-71033-9_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T00:06:08Z","timestamp":1725321968000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-71033-9_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031710322","9783031710339"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-71033-9_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"31 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cwi.nl\/en\/groups\/networks-and-optimization\/events\/sagt-2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}