{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:28:37Z","timestamp":1778498917164,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,15]],"date-time":"2014-10-15T00:00:00Z","timestamp":1413331200000},"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":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9942-0","type":"journal-article","created":{"date-parts":[[2014,10,14]],"date-time":"2014-10-14T15:47:04Z","timestamp":1413301624000},"page":"177-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Parametric Packing of Selfish Items and the Subset Sum Algorithm"],"prefix":"10.1007","volume":"74","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Kleiman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juli\u00e1n","family":"Mestre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,15]]},"reference":[{"issue":"2","key":"9942_CR1","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.geb.2008.03.005","volume":"65","author":"N Andelman","year":"2009","unstructured":"Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. Games Econ. Behav. 65(2), 289\u2013317 (2009)","journal-title":"Games Econ. Behav."},{"key":"9942_CR2","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V.: On the packing of selfish items. In Proc. of the 20th International Parallel and Distributed Processing Symposium (IPDPS2006). IEEE, (2006). 9 pages","DOI":"10.1109\/IPDPS.2006.1639283"},{"issue":"2","key":"9942_CR3","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0167-6377(03)00092-0","volume":"32","author":"A Caprara","year":"2004","unstructured":"Caprara, A., Pferschy, U.: Worst-case analysis of the subset sum algorithm for bin packing. Oper. Res. Lett. 32(2), 159\u2013166 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9942_CR4","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.ipl.2005.04.005","volume":"96","author":"A Caprara","year":"2005","unstructured":"Caprara, A., Pferschy, U.: Modified subset sum heuristics for bin packing. Inf. Process. Lett. 96(1), 18\u201323 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9942_CR5","volume-title":"Handbook of approximation algorithms and metaheuristics, chapter 32","author":"E Coffman Jr","year":"2007","unstructured":"Coffman Jr, E., Csirik, J.: Performance guarantees for one-dimensional bin packing. In: Gonzalez, T.F. (ed.) Handbook of approximation algorithms and metaheuristics, chapter 32. Chapman & Hall\/Crc, London (2007)"},{"key":"9942_CR6","volume-title":"Handbook of Approximation Algorithms and Metaheuristics, chapter 33","author":"J Csirik","year":"2007","unstructured":"Csirik, J., Leung, J.Y.-T.: Variants of classical one-dimensional bin packing. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics, chapter 33. Chapman & Hall\/Crc, London (2007)"},{"key":"9942_CR7","doi-asserted-by":"crossref","unstructured":"Czumaj, A., V\u00f6cking, B.: Tight bounds for worst-case equilibria. ACM Trans. Algorithms 3(1), 4:1\u20134:17 (2007)","DOI":"10.1145\/1219944.1219949"},{"issue":"2","key":"9942_CR8","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/s00453-009-9348-6","volume":"60","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Kleiman, E.: Selfish bin packing. Algorithmica 60(2), 368\u2013394 (2011)","journal-title":"Algorithmica"},{"key":"9942_CR9","doi-asserted-by":"crossref","unstructured":"Fiat, A., Kaplan, H., Levy, M., Olonetsky, S.: Strong price of anarchy for machine load balancing. In Proceedings of the 34th international colloquium on automata, languages and programming (ICALP2007), pages 583\u2013594, (2007)","DOI":"10.1007\/978-3-540-73420-8_51"},{"key":"9942_CR10","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1080\/095372899232894","volume":"10","author":"JND Gupta","year":"1999","unstructured":"Gupta, J.N.D., Ho, J.C.: A new heuristic algorithm for the one-dimensional bin-packing problem. Prod. Plan. Control 10, 598\u2013603 (1999)","journal-title":"Prod. Plan. Control"},{"key":"9942_CR11","doi-asserted-by":"crossref","unstructured":"Graham, RL.: Bounds on multiprocessing anomalies and related packing algorithms. In Proc. of the 1972 Spring Joint Computer Conference, pages 205\u2013217, (1972)","DOI":"10.1145\/1478873.1478901"},{"key":"9942_CR12","doi-asserted-by":"crossref","unstructured":"Immorlica, N., Mahdian, M., Mirrokni, VS.: Cycle cover with short cycles. In Proc. of the 22th Annual Symposium on Theoretical Aspects of Computer Science (STACS2005), pages 641\u2013653, (2005)","DOI":"10.1007\/978-3-540-31856-9_53"},{"issue":"6","key":"9942_CR13","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"issue":"4","key":"9942_CR14","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A.J., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299\u2013325 (1974)","journal-title":"SIAM J. Comput."},{"key":"9942_CR15","doi-asserted-by":"crossref","unstructured":"Karp, RM.: Reducibility among combinatorial problems. In complexity of computer computations, page 85-103, (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9942_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack problems. Springer, Berlin (2004)"},{"key":"9942_CR17","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, CH.: Worst-case equilibria. In Proc. of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS1999), pages 404\u2013413, (1999)","DOI":"10.1007\/3-540-49116-3_38"},{"key":"9942_CR18","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple online bin packing algorithm. J. ACM 32, 562\u2013572 (1985)","journal-title":"J. ACM"},{"issue":"1","key":"9942_CR19","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00453-006-0056-1","volume":"48","author":"M Mavronicolas","year":"2007","unstructured":"Mavronicolas, M., Spirakis, P.G.: The price of selfish routing. Algorithmica 48(1), 91\u2013126 (2007)","journal-title":"Algorithmica"},{"key":"9942_CR20","volume-title":"Selfish routing and the price of anarchy","author":"T Roughgarden","year":"2005","unstructured":"Roughgarden, T.: Selfish routing and the price of anarchy. MIT Press, Cambridge (2005)"},{"issue":"2","key":"9942_CR21","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T Roughgarden","year":"2002","unstructured":"Roughgarden, T., Tardos, \u00c9.: How bad is selfish routing? J. ACM 49(2), 236\u2013259 (2002)","journal-title":"J. ACM"},{"key":"9942_CR22","unstructured":"Ullman, JD.: The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ, (1971)"},{"key":"9942_CR23","doi-asserted-by":"crossref","unstructured":"Yu, G., Zhang, G.: Bin packing of selfish items. In The 4th international workshop on internet and network economics (WINE2008), pages 446\u2013453, (2008)","DOI":"10.1007\/978-3-540-92185-1_50"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9942-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9942-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9942-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T04:14:29Z","timestamp":1746418469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9942-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,15]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9942"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9942-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,15]]}}}