{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T07:36:27Z","timestamp":1783150587354,"version":"3.54.6"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031206238","type":"print"},{"value":"9783031206245","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-20624-5_13","type":"book-chapter","created":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T15:18:05Z","timestamp":1666970285000},"page":"204-221","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Schemes for\u00a0Packing Problems with\u00a0$$\\ell _p$$-norm Diversity Constraints"],"prefix":"10.1007","author":[{"given":"Waldo","family":"G\u00e1lvez","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"V\u00edctor","family":"Verdugo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Cohen-Addad, V., Lee, E., Manurangsi, P.: Improved approximation algorithms and lower bounds for search-diversification problems. In: 49th International Colloquium on Automata, Languages, and Programming (ICALP), vol. 229, pp. 7:1\u20137:18 (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2022.7","DOI":"10.4230\/LIPIcs.ICALP.2022.7"},{"issue":"6","key":"13_CR2","doi-asserted-by":"publisher","first-page":"1750","DOI":"10.1007\/s00453-021-00801-2","volume":"83","author":"S Albers","year":"2021","unstructured":"Albers, S., Khan, A., Ladewig, L.: Improved online algorithms for knapsack and GAP in the random order model. Algorithmica 83(6), 1750\u20131785 (2021)","journal-title":"Algorithmica"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Anegg, G., Angelidakis, H., Kurpisz, A., Zenklusen, R.: A technique for obtaining true approximations for k-center with covering constraints. In: Bienstock, D., Zambelli, G. (eds.) Integer Programming and Combinatorial Optimization, pp. 52\u201365 (2020)","DOI":"10.1007\/978-3-030-45771-6_5"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Grove, E.F., Kao, M., Krishnan, P., Vitter, J.S.: Load balancing in the $$l_p$$ norm. In: 36th Annual Symposium on Foundations of Computer Science (FOCS), pp. 383\u2013391. IEEE Computer Society (1995)","DOI":"10.1109\/SFCS.1995.492494"},{"key":"13_CR5","unstructured":"Bandyapadhyay, S., Inamdar, T., Pai, S., Varadarajan, K.R.: A constant approximation for colorful k-center. In: 27th Annual European Symposium on Algorithms (ESA), vol. 144, pp. 12:1\u201312:14 (2019)"},{"issue":"1","key":"13_CR6","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4086\/toc.2012.v008a024","volume":"8","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: Solving packing integer programs via randomized rounding with alterations. Theory Comput. 8(1), 533\u2013565 (2012)","journal-title":"Theory Comput."},{"key":"13_CR7","doi-asserted-by":"publisher","unstructured":"Bansal, N., Pruhs, K.: Server scheduling in the weighted $$\\ell _p$$ Norm. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 434\u2013443. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24698-5_47","DOI":"10.1007\/978-3-540-24698-5_47"},{"key":"13_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105693","volume":"143","author":"V Cacchiani","year":"2022","unstructured":"Cacchiani, V., Iori, M., Locatelli, A., Martello, S.: Knapsack problems - an overview of recent advances, Part II: multiple, multidimensional, and quadratic knapsack problems. Comput. Oper. Res. 143, 105693 (2022)","journal-title":"Comput. Oper. Res."},{"key":"13_CR9","unstructured":"Celis, E., Keswani, V., Straszak, D., Deshpande, A., Kathuria, T., Vishnoi, N.: Fair and diverse DPP-based data summarization. In: Dy, J., Krause, A. (eds.) Proceedings of the 35th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 80, pp. 716\u2013725. PMLR, 10\u201315 July 2018"},{"key":"13_CR10","unstructured":"Celis, L.E., Huang, L., Keswani, V., Vishnoi, N.K.: Fair classification with noisy protected attributes: a framework with provable guarantees (2021)"},{"issue":"1","key":"13_CR11","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1146\/annurev-ecolsys-120213-091540","volume":"45","author":"A Chao","year":"2014","unstructured":"Chao, A., Chiu, C.H., Jost, L.: Unifying species diversity, phylogenetic diversity, functional diversity, and related similarity and differentiation measures through hill numbers. Annu. Rev. Ecol. Evol. Syst. 45(1), 297\u2013324 (2014)","journal-title":"Annu. Rev. Ecol. Evol. Syst."},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Chasalow, K., Levy, K.: Representativeness in statistics, politics, and machine learning. In: Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT 2021, pp. 77\u201389. Association for Computing Machinery, New York (2021)","DOI":"10.1145\/3442188.3445872"},{"issue":"3","key":"13_CR13","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"C Chekuri","year":"2005","unstructured":"Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713\u2013728 (2005)","journal-title":"SIAM J. Comput."},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Chen, L., Tao, L., Verschae, J.: Tight running times for minimum $$\\ell _p$$-norm load balancing: beyond exponential dependencies on $$1\/\\varepsilon $$. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 275\u2013315. SIAM (2022)","DOI":"10.1137\/1.9781611977073.14"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Chi, N., Lurie, E., Mulligan, D.K.: Reconfiguring diversity and inclusion for AI ethics. In: Proceedings of the 2021 AAAI\/ACM Conference on AI, Ethics, and Society, pp. 447\u2013457. Association for Computing Machinery, New York (2021)","DOI":"10.1145\/3461702.3462622"},{"key":"13_CR16","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS 2017, pp. 5036\u20135044. Curran Associates Inc., Red Hook (2017)"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63\u201379 (2017)","journal-title":"Comput. Sci. Rev."},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Daly, A.J., Baetens, J.M., De Baets, B.: Ecological diversity: measuring the unmeasurable. Mathematics 6(7) (2018)","DOI":"10.3390\/math6070119"},{"issue":"2","key":"13_CR19","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1089\/big.2016.0054","volume":"5","author":"M Drosou","year":"2017","unstructured":"Drosou, M., Jagadish, H., Pitoura, E., Stoyanovich, J.: Diversity in big data: a review. Big Data 5(2), 73\u201384 (2017)","journal-title":"Big Data"},{"issue":"1","key":"13_CR20","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/0377-2217(84)90053-5","volume":"15","author":"AM Frieze","year":"1984","unstructured":"Frieze, A.M., Clarke, M.R.B.: Approximation algorithms for the m-dimensional 0\u20131 knapsack problem: worst-case and probabilistic analyses. Eur. J. Oper. Res. 15(1), 100\u2013109 (1984)","journal-title":"Eur. J. Oper. Res."},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Ghadiri, M., Samadi, S., Vempala, S.: Fair k-means clustering (2020). arXiv","DOI":"10.1145\/3442188.3445906"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"G\u00e1lvez, W., Grandoni, F., Heydrich, S., Ingala, S., Khan, A., Wiese, A.: Approximating geometric knapsack via l-packings. ACM Trans. Algorithms 17(4), 33:1\u201333:67 (2021)","DOI":"10.1145\/3473713"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"G\u00e1lvez, W., Grandoni, F., Khan, A., Ram\u00edrez-Romero, D., Wiese, A.: Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple l-shapes, spirals, and more. In: 37th International Symposium on Computational Geometry (SoCG), vol. 189, pp. 39:1\u201339:17 (2021)","DOI":"10.1145\/3473713"},{"key":"13_CR24","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^\\varepsilon $$. Electron. Colloq. Comput. Complex. (38) (1997)"},{"issue":"4","key":"13_CR25","first-page":"61","volume":"24","author":"CH Heip","year":"1998","unstructured":"Heip, C.H., Herman, P.M., Soetaert, K.: Indices of diversity and evenness. Oceanis 24(4), 61\u201388 (1998)","journal-title":"Oceanis"},{"issue":"2","key":"13_CR26","doi-asserted-by":"publisher","first-page":"427","DOI":"10.2307\/1934352","volume":"54","author":"MO Hill","year":"1973","unstructured":"Hill, M.O.: Diversity and evenness: a unifying notation and its consequences. Ecology 54(2), 427\u2013432 (1973)","journal-title":"Ecology"},{"key":"13_CR27","unstructured":"Huang, L., Vishnoi, N.: Stable and fair classification. In: Chaudhuri, K., Salakhutdinov, R. (eds.) Proceedings of the 36th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 97, pp. 2879\u20132890. PMLR, 09\u201315 June 2019"},{"issue":"4","key":"13_CR28","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 subset problems. J. ACM 22(4), 463\u2013468 (1975)","journal-title":"J. ACM"},{"issue":"4","key":"13_CR29","doi-asserted-by":"publisher","first-page":"1392","DOI":"10.1137\/080731207","volume":"39","author":"K Jansen","year":"2009","unstructured":"Jansen, K.: Parameterized approximation scheme for the multiple knapsack problem. SIAM J. Comput. 39(4), 1392\u20131412 (2009)","journal-title":"SIAM J. Comput."},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Jia, X., Sheth, K., Svensson, O.: Fair colorful k-center clustering. In: Bienstock, D., Zambelli, G. (eds.) Integer Programming and Combinatorial Optimization, pp. 209\u2013222 (2020)","DOI":"10.1007\/978-3-030-45771-6_17"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"13_CR32","doi-asserted-by":"publisher","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack problems. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24777-7","DOI":"10.1007\/978-3-540-24777-7"},{"issue":"1","key":"13_CR33","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1111\/j.0030-1299.2005.13735.x","volume":"109","author":"CJ Keylock","year":"2005","unstructured":"Keylock, C.J.: Simpson diversity and the Shannon-Wiener index as special cases of a generalized entropy. Oikos 109(1), 203\u2013207 (2005)","journal-title":"Oikos"},{"issue":"4","key":"13_CR34","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"EL Lawler","year":"1979","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4), 339\u2013356 (1979). https:\/\/doi.org\/10.1287\/moor.4.4.339","journal-title":"Math. Oper. Res."},{"issue":"2","key":"13_CR35","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1287\/moor.9.2.244","volume":"9","author":"MJ Magazine","year":"1984","unstructured":"Magazine, M.J., Chern, M.: A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res. 9(2), 244\u2013247 (1984)","journal-title":"Math. Oper. Res."},{"key":"13_CR36","doi-asserted-by":"crossref","unstructured":"Mitchell, M., et al.: Diversity and inclusion metrics in subset selection. In: Proceedings of the AAAI\/ACM Conference on AI, Ethics, and Society, AIES 2020, pp. 117\u2013123. Association for Computing Machinery, New York (2020)","DOI":"10.1145\/3375627.3375832"},{"key":"13_CR37","unstructured":"Naori, D., Raz, D.: Online multidimensional packing problems in the random-order model. In: 30th International Symposium on Algorithms and Computation (ISAAC), vol. 149, pp. 10:1\u201310:15 (2019)"},{"key":"13_CR38","doi-asserted-by":"crossref","unstructured":"Papachristou, M., Kleinberg, J.M.: Allocating stimulus checks in times of crisis. In: The ACM Web Conference (WWW), pp. 16\u201326. ACM (2022)","DOI":"10.1145\/3485447.3512047"},{"key":"13_CR39","unstructured":"Patel, D., Khan, A., Louis, A.: Group fairness for knapsack problems. In: 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1001\u20131009. ACM (2021)"},{"issue":"10\u201311","key":"13_CR40","doi-asserted-by":"publisher","first-page":"1591","DOI":"10.1016\/j.dam.2012.02.020","volume":"160","author":"B Patt-Shamir","year":"2012","unstructured":"Patt-Shamir, B., Rawitz, D.: Vector bin packing with multiple-choice. Discrete Appl. Math. 160(10\u201311), 1591\u20131600 (2012). https:\/\/doi.org\/10.1016\/j.dam.2012.02.020","journal-title":"Discrete Appl. Math."},{"key":"13_CR41","doi-asserted-by":"crossref","unstructured":"Perez-Salazar, S., Torrico, A., Verdugo, V.: Preserving diversity when partitioning: a geometric approach. In: ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO), pp. 1\u201311 (2021)","DOI":"10.1145\/3465416.3483297"},{"issue":"1","key":"13_CR42","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":"13_CR43","unstructured":"Sharma, E.: Harmonic algorithms for packing D-dimensional cuboids into bins. In: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), vol. 213, pp. 32:1\u201332:22 (2021)"},{"issue":"4148","key":"13_CR44","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1038\/163688a0","volume":"163","author":"EH Simpson","year":"1949","unstructured":"Simpson, E.H.: Measurement of diversity. Nature 163(4148), 688 (1949)","journal-title":"Nature"},{"key":"13_CR45","doi-asserted-by":"publisher","unstructured":"Zhang, H., Jansen, K.: Scheduling malleable tasks. In: Handbook of Approximation Algorithms and Metaheuristics (2007). https:\/\/doi.org\/10.1201\/9781420010749.ch45","DOI":"10.1201\/9781420010749.ch45"},{"issue":"1","key":"13_CR46","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Lecture Notes in Computer Science","LATIN 2022: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-20624-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T19:55:53Z","timestamp":1728244553000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20624-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206238","9783031206245"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20624-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"29 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guanajuato","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/delta.cs.cinvestav.mx\/~francisco\/Latin22\/","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":"114","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":"46","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":"40% - 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":"4","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":"8.7","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}