{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:19:01Z","timestamp":1742923141582,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_79","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"973-984","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A $$(2+\\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem"],"prefix":"10.1007","author":[{"given":"Tobias","family":"M\u00f6mke","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"79_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 400\u2013409. IEEE (2013)","DOI":"10.1109\/FOCS.2013.50"},{"key":"79_CR2","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: A quasi-PTAS for the two-dimensional geometric knapsack problem. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 1491\u20131505 (2015)","DOI":"10.1137\/1.9781611973730.98"},{"key":"79_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Computational Geometry 11, 209\u2013218 (1998)","journal-title":"Computational Geometry"},{"key":"79_CR4","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing $$2+\\epsilon $$ approximation for unsplittable flow on a path. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014) (2014)","DOI":"10.1137\/1.9781611973402.3"},{"key":"79_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-10631-6_10","volume-title":"Algorithms and Computation","author":"N Bansal","year":"2009","unstructured":"Bansal, N., Caprara, A., Jansen, K., Pr\u00e4del, L., Sviridenko, M.: A structural lemma in 2-dimensional packing, and its implications on approximability. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 77\u201386. Springer, Heidelberg (2009)"},{"key":"79_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: STOC, pp. 721\u2013729. ACM (2006)","DOI":"10.1145\/1132516.1132617"},{"key":"79_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, R.: A logarithmic approximation for unsplittable flow on line graphs. In: SODA, pp. 702\u2013709 (2009)","DOI":"10.1137\/1.9781611973068.77"},{"issue":"5","key":"79_CR8","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. Journal of the ACM (JACM) 48(5), 1069\u20131090 (2001)","journal-title":"Journal of the ACM (JACM)"},{"issue":"1","key":"79_CR9","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s00453-007-9121-7","volume":"54","author":"R Bar-Yehuda","year":"2009","unstructured":"Bar-Yehuda, R., Beder, M., Cohen, Y., Rawitz, D.: Resource allocation in bounded degree trees. Algorithmica 54(1), 89\u2013106 (2009)","journal-title":"Algorithmica"},{"key":"79_CR10","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Beder, M., Rawitz, D.: A constant factor approximation algorithm for the storage allocation problem. In: Proceedings of the 25th ACM symposium on Parallelism in Algorithms and Architectures, pp. 204\u2013213. ACM (2013)","DOI":"10.1145\/2486159.2486177"},{"key":"79_CR11","doi-asserted-by":"crossref","unstructured":"Batra, J., Garg, N., Kumar, A., M\u00f6mke, T., Wiese, A.: New approximation schemes for unsplittable flow on a path. In: SODA, pp. 47\u201358 (2015)","DOI":"10.1137\/1.9781611973730.5"},{"key":"79_CR12","unstructured":"Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Improved approximation algorithms for rectangle tiling and packing. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 427\u2013436. Society for Industrial and Applied Mathematics (2001)"},{"issue":"3","key":"79_CR13","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0167-6377(99)00010-3","volume":"24","author":"D Bertsimas","year":"1999","unstructured":"Bertsimas, D., Teo, C.-P., Vohra, R.: On dependent randomized rounding algorithms. Oper. Res. Lett. 24(3), 105\u2013114 (1999)","journal-title":"Oper. Res. Lett."},{"key":"79_CR14","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1137\/120868360","volume":"43","author":"P Bonsma","year":"2014","unstructured":"Bonsma, P., Schulz, J., Wiese, A.: A constant-factor approximation algorithm for unsplittable flow on paths. SIAM Journal on Computing 43, 767\u2013799 (2014)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"79_CR15","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1137\/S0097539703423941","volume":"33","author":"AL Buchsbaum","year":"2004","unstructured":"Buchsbaum, A.L., Karloff, H., Kenyon, C., Reingold, N., Thorup, M.: Opt versus load in dynamic storage allocation. SIAM Journal on Computing 33(3), 632\u2013646 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"79_CR16","doi-asserted-by":"crossref","first-page":"48:1","DOI":"10.1145\/2000807.2000816","volume":"7","author":"G C\u0103linescu","year":"2011","unstructured":"C\u0103linescu, G., Chakrabarti, A., Karloff, H.J., Rabani, Y.: An improved approximation algorithm for resource allocation. ACM Transactions on Algorithms 7, 48:1\u201348:7 (2011)","journal-title":"ACM Transactions on Algorithms"},{"key":"79_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s00453-006-1210-5","volume":"47","author":"A Chakrabarti","year":"2007","unstructured":"Chakrabarti, A., Chekuri, C., Gupta, A., Kumar, A.: Approximation algorithms for the unsplittable flow problem. Algorithmica 47, 53\u201378 (2007)","journal-title":"Algorithmica"},{"key":"79_CR18","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pp. 892\u2013901. SIAM (2009)","DOI":"10.1137\/1.9781611973068.97"},{"issue":"2","key":"79_CR19","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry 48(2), 373\u2013392 (2012)","journal-title":"Discrete & Computational Geometry"},{"key":"79_CR20","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs. In: APPROX-RANDOM, pp. 42\u201355 (2009)","DOI":"10.1007\/978-3-642-03685-9_4"},{"key":"79_CR21","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Mydlarz, M., Shepherd, F.: Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms 3, (2007)","DOI":"10.1145\/1273340.1273343"},{"issue":"5","key":"79_CR22","first-page":"501","volume":"34","author":"B Chen","year":"2002","unstructured":"Chen, B., Hassin, R., Tzur, M.: Allocation of bandwidth and storage. IIE Transactions 34(5), 501\u2013507 (2002)","journal-title":"IIE Transactions"},{"issue":"3","key":"79_CR23","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s00224-009-9184-8","volume":"47","author":"T Erlebach","year":"2010","unstructured":"Erlebach, T., Hagerup, T., Jansen, K., Minzlaff, M., Wolff, A.: Trimming of graphs, with application to point labeling. Theory of Computing Systems 47(3), 613\u2013636 (2010)","journal-title":"Theory of Computing Systems"},{"key":"79_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/11549345_31","volume-title":"Mathematical Foundations of Computer Science 2005","author":"AV Fishkin","year":"2005","unstructured":"Fishkin, A.V., Gerber, O., Jansen, K., Solis-Oba, R.: Packing weighted rectangles into a square. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 352\u2013363. Springer, Heidelberg (2005)"},{"key":"79_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-61680-2_46","volume-title":"Algorithms - ESA \u201996","author":"J Gergov","year":"1996","unstructured":"Gergov, J.: Approximation algorithms for dynamic storage allocation. In: D\u00edaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 52\u201361. Springer, Heidelberg (1996)"},{"key":"79_CR26","unstructured":"Gergov, J.: Algorithms for compile-time memory optimization. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 907\u2013908. Society for Industrial and Applied Mathematics (1999)"},{"key":"79_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-540-74456-6_11","volume-title":"Mathematical Foundations of Computer Science 2007","author":"K Jansen","year":"2007","unstructured":"Jansen, K., Solis-Oba, R.: New approximability results for 2-dimensional packing problems. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 103\u2013114. Springer, Heidelberg (2007)"},{"key":"79_CR28","unstructured":"Jansen, K., Zhang, G.: On rectangle packing: maximizing benefits. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 204\u2013213. Society for Industrial and Applied Mathematics (2004)"},{"key":"79_CR29","unstructured":"Khanna, S., Muthukrishnan, S., Paterson, M.: On approximating rectangle tiling and packing. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 384\u2013393. SIAM (1998)"},{"issue":"4","key":"79_CR30","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1137\/0401048","volume":"1","author":"HA Kierstead","year":"1988","unstructured":"Kierstead, H.A.: The linearity of first-fit coloring of interval graphs. SIAM Journal on Discrete Mathematics 1(4), 526\u2013530 (1988)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"79_CR31","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0012-365X(91)90011-P","volume":"88","author":"HA Kierstead","year":"1991","unstructured":"Kierstead, H.A.: A polynomial time approximation algorithm for dynamic storage allocation. Discrete Mathematics 88(2), 231\u2013237 (1991)","journal-title":"Discrete Mathematics"},{"issue":"6","key":"79_CR32","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1016\/j.dam.2011.07.023","volume":"160","author":"D Knipe","year":"2012","unstructured":"Knipe, D.: Trimming weighted graphs of bounded treewidth. Discrete Applied Mathematics 160(6), 902\u2013912 (2012)","journal-title":"Discrete Applied Mathematics"},{"key":"79_CR33","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0304-3975(98)00336-3","volume":"246","author":"F Nielsen","year":"2000","unstructured":"Nielsen, F.: Fast stabbing of boxes in high dimensions. Theor. Comp. Sc. 246, 53\u201372 (2000)","journal-title":"Theor. Comp. Sc."},{"key":"79_CR34","unstructured":"Phillips, C.A., Uma, R.N., Wein, J.: Off-line admission control for general scheduling problems. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 879\u2013888. ACM (2000)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_79","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T04:13:59Z","timestamp":1675138439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_79"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_79","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}