{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T06:17:58Z","timestamp":1725776278297},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,3,3]],"date-time":"2016-03-03T00:00:00Z","timestamp":1456963200000},"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":[[2017,4]]},"DOI":"10.1007\/s00453-016-0137-8","type":"journal-article","created":{"date-parts":[[2016,3,3]],"date-time":"2016-03-03T14:16:14Z","timestamp":1457014574000},"page":"1105-1127","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Constant Factor Approximation Algorithm for the Storage Allocation Problem"],"prefix":"10.1007","volume":"77","author":[{"given":"Reuven","family":"Bar-Yehuda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Beder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,3,3]]},"reference":[{"key":"137_CR1","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: Constant integrality gap LP formulations of unsplittable flow on a path. In: 16th International Integer Programming and Combinatorial Optimization Conference, volume 7801 of LNCS, pp. 25\u201336 (2013)","DOI":"10.1007\/978-3-642-36694-9_3"},{"key":"137_CR2","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing $$(2+\\varepsilon )$$ ( 2 + \u03b5 ) -approximation for unsplittable flow on a path. In: 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 26\u201341 (2014)","DOI":"10.1137\/1.9781611973402.3"},{"key":"137_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-ptas for unsplittable flow on line graphs. In: 38th Annual ACM Symposium on the Theory of Computing, pp. 721\u2013729 (2006)","DOI":"10.1145\/1132516.1132617"},{"issue":"1","key":"137_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2532645","volume":"10","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, M.R.: A logarithmic approximation for unsplittable flow on line graphs. ACM Trans. Algorithms 10(1), 1 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"5","key":"137_CR5","doi-asserted-by":"crossref","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., Shieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069\u20131090 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"137_CR6","doi-asserted-by":"crossref","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":"137_CR7","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Beder, M., Rawitz, D.: A constant factor approximation algorithm for the storage allocation problem. In: 25th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 204\u2013213 (2013)","DOI":"10.1145\/2486159.2486177"},{"key":"137_CR8","first-page":"27","volume":"25","author":"R Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Ann. Discret. Math. 25, 27\u201346 (1985)","journal-title":"Ann. Discret. Math."},{"key":"137_CR9","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: 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 47\u201358 (2015)","DOI":"10.1137\/1.9781611973730.5"},{"issue":"2","key":"137_CR10","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1137\/120868360","volume":"43","author":"PS Bonsma","year":"2014","unstructured":"Bonsma, P.S., Schulz, J., Wiese, A.: A constant-factor approximation algorithm for unsplittable flow on paths. SIAM J. Comput. 43(2), 767\u2013799 (2014)","journal-title":"SIAM J. Comput."},{"key":"137_CR11","unstructured":"Buchsbaum, A.L., Efrat, A., Jain, S., Venkatasubramanian, S., Yi, K.: Restricted strip covering and the sensor cover problem. Technical report. arXiv:cs\/0605102v1 . CoRR (2008)"},{"issue":"3","key":"137_CR12","doi-asserted-by":"crossref","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 J. Comput. 33(3), 632\u2013646 (2004)","journal-title":"SIAM J. Comput."},{"key":"137_CR13","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chakrabarti, A., Karloff, H.J., Rabani, Y.: Improved approximation algorithms for resource allocation. In: 9th International Integer Programming and Combinatorial Optimization Conference, vol. 2337 of LNCS, pp. 401\u2013414 (2002)","DOI":"10.1007\/3-540-47867-1_28"},{"issue":"1","key":"137_CR14","doi-asserted-by":"crossref","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(1), 53\u201378 (2007)","journal-title":"Algorithmica"},{"key":"137_CR15","unstructured":"Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs. http:\/\/www.cs.princeton.edu\/aene\/papers\/ufp-full.pdf"},{"key":"137_CR16","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs. In: 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 5687 of LNCS, pp. 42\u201355 (2009)","DOI":"10.1007\/978-3-642-03685-9_4"},{"issue":"3","key":"137_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1273340.1273343","volume":"3","author":"C Chekuri","year":"2007","unstructured":"Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3(3), 1\u201323 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"137_CR18","first-page":"501","volume":"34","author":"B Chen","year":"2002","unstructured":"Chen, B., Hassin, R., Tzur, M.: Allocation of bandwidth and storage. IIE Trans. 34, 501\u2013507 (2002)","journal-title":"IIE Trans."},{"issue":"4","key":"137_CR19","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1007\/s00453-011-9502-9","volume":"63","author":"M Chrobak","year":"2012","unstructured":"Chrobak, M., Woeginger, G.J., Makino, K., Xu, H.: Caching is hard\u2014even in the fault model. Algorithmica 63(4), 781\u2013794 (2012)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"137_CR20","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/S0304-3975(99)00152-8","volume":"255","author":"T Erlebach","year":"2001","unstructured":"Erlebach, T., Jansen, K.: The complexity of path coloring and call scheduling. Theor. Comput. Sci. 255(1\u20132), 33\u201350 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"137_CR21","doi-asserted-by":"crossref","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$$ m -dimensional $$0-1$$ 0 - 1 knapsack problem: worst-case and probabilistic analyses. Eur. J. Oper. Res. 15, 100\u2013109 (1984)","journal-title":"Eur. J. Oper. Res."},{"key":"137_CR22","unstructured":"Friggstad, Z., Gao, Z.: On linear programming relaxations for unsplittable flow in trees. In: 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 40 of LIPIcs, pp. 265\u2013283 (2015)"},{"key":"137_CR23","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"137_CR24","unstructured":"Gergov, J.: Algorithms for compile-time memory optimization. In: 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 907\u2013908 (1999)"},{"key":"137_CR25","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, Cambridge (1980)"},{"key":"137_CR26","doi-asserted-by":"crossref","unstructured":"Leonardi, S., Marchetti-Spaccamela, A., Vitaletti, A.: Approximation algorithms for bandwidth and storage allocation problems under real time constraints. In: 20th Conference on Foundations of Software Technology and Theoretical Computer Science, vol. 1974 of LNCS, pp. 409\u2013420 (2000)","DOI":"10.1007\/3-540-44450-5_33"},{"issue":"3","key":"137_CR27","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417\u2013427 (1983)","journal-title":"J. ACM"},{"key":"137_CR28","doi-asserted-by":"crossref","unstructured":"M\u00f6mke T., Wiese A., A $$(2+\\epsilon )$$ ( 2 + \u03f5 ) -approximation algorithm for the storage allocation problem. In: 42nd Annual International Colloquium on Automata, Languages, and Programming, vol. 9134 of LNCS, pp. 973\u2013984 (2015)","DOI":"10.1007\/978-3-662-47672-7_79"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0137-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0137-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0137-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0137-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T02:33:30Z","timestamp":1567650810000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0137-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,3]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["137"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0137-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,3]]}}}