{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T06:24:59Z","timestamp":1725776699405},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T00:00:00Z","timestamp":1557187200000},"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":[[2019,8]]},"DOI":"10.1007\/s00453-019-00582-9","type":"journal-article","created":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T20:47:18Z","timestamp":1557262038000},"page":"3217-3244","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Flexible Resource Allocation to Interval Jobs"],"prefix":"10.1007","volume":"81","author":[{"given":"Dmitriy","family":"Katz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,7]]},"reference":[{"key":"582_CR1","doi-asserted-by":"crossref","unstructured":"Albers, S., Arora, S., Khanna, S.: Page replacement for general caching problems. In: SODA, pp. 31\u201340 (1999)","DOI":"10.1111\/an.1999.40.5.31.4"},{"key":"582_CR2","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 (2006)","DOI":"10.1145\/1132516.1132617"},{"issue":"5","key":"582_CR3","first-page":"735","volume":"48","author":"A Bar-Noy","year":"2000","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. JACM 48(5), 735\u2013744 (2000)","journal-title":"JACM"},{"issue":"1","key":"582_CR4","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"},{"issue":"4","key":"582_CR5","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1007\/s00453-016-0137-8","volume":"77","author":"R Bar-Yehuda","year":"2017","unstructured":"Bar-Yehuda, R., Beder, M., Rawitz, D.: A constant factor approximation algorithm for the storage allocation problem. Algorithmica 77(4), 1105\u20131127 (2017)","journal-title":"Algorithmica"},{"key":"582_CR6","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"},{"issue":"2","key":"582_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"LA Belady","year":"1966","unstructured":"Belady, L.A.: A study of replacement algorithms for virtual-storage computer. IBM Syst. J. 5(2), 78\u2013101 (1966)","journal-title":"IBM Syst. J."},{"issue":"3","key":"582_CR8","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1137\/S0097539703423941","volume":"33","author":"AL Buchsbaum","year":"2004","unstructured":"Buchsbaum, A.L., Karloff, H.J., 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."},{"issue":"4","key":"582_CR9","doi-asserted-by":"crossref","first-page":"48","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 Trans. Algorithms 7(4), 48 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"582_CR10","doi-asserted-by":"crossref","unstructured":"Chakaravarthy, V.T., Choudhury, A.R., Gupta, S., Roy, S., Sabharwal, Y.: Improved algorithms for resource allocation under varying capacity. In: ESA, pp. 222\u2013234 (2014)","DOI":"10.1007\/978-3-662-44777-2_19"},{"issue":"3","key":"582_CR11","doi-asserted-by":"publisher","first-page":"27","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), 27 (2007)","journal-title":"ACM Trans. Algorithms"},{"issue":"5","key":"582_CR12","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(5), 501\u2013507 (2002)","journal-title":"IIE Trans."},{"issue":"4","key":"582_CR13","doi-asserted-by":"publisher","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"},{"key":"582_CR14","doi-asserted-by":"crossref","unstructured":"Gerstel, O.: Flexible use of spectrum and photonic grooming. In: Photonics in Switching (2010)","DOI":"10.1364\/PS.2010.PMD3"},{"key":"582_CR15","doi-asserted-by":"crossref","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A., Zhou, H.: A (5\/3+$$\\epsilon $$) approximation for unsplittable flow on a path: placing small tasks into boxes. In: STOC, pp. 607\u2013619 (2018)","DOI":"10.1145\/3188745.3188894"},{"key":"582_CR16","doi-asserted-by":"crossref","unstructured":"Jain, N., Menache, I., Naor, J., Yaniv, J.: A truthful mechanism for value-based scheduling in cloud computing. In: SAGT, pp. 178\u2013189 (2011)","DOI":"10.1007\/978-3-642-24829-0_17"},{"issue":"3","key":"582_CR17","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/s00224-013-9449-0","volume":"54","author":"N Jain","year":"2014","unstructured":"Jain, N., Menache, I., Naor, J., Yaniv, J.: A truthful mechanism for value-based scheduling in cloud computing. Theory Comput. Syst. 54(3), 388\u2013406 (2014)","journal-title":"Theory Comput. Syst."},{"key":"582_CR18","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1109\/MCOM.2009.5307468","volume":"47","author":"M Jinno","year":"2009","unstructured":"Jinno, M., Takara, H., Kozicki, B., Tsukishima, Y., Sone, Y., Matsuoka, S.: Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies. Comm. Mag. 47, 66\u201373 (2009)","journal-title":"Comm. Mag."},{"key":"582_CR19","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"582_CR20","volume-title":"The Art of Computer Programming, Vol. 1: Fundamental Algorithms","author":"D Knuth","year":"1973","unstructured":"Knuth, D.: The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd edn. Addison-Wesley, Boston (1973)","edition":"2"},{"issue":"5","key":"582_CR21","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1002\/nav.20231","volume":"54","author":"AW Kolen","year":"2007","unstructured":"Kolen, A.W., Lenstra, J.K., Papadimitriou, C.H., Spieksma, F.C.: Interval scheduling: a survey. Naval Res. Logist. 54(5), 530\u2013543 (2007)","journal-title":"Naval Res. Logist."},{"key":"582_CR22","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: FSTTCS, pp. 409\u2013420 (2000)","DOI":"10.1007\/3-540-44450-5_33"},{"issue":"1","key":"582_CR23","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0020-0190(98)00080-5","volume":"67","author":"V Liberatore","year":"1998","unstructured":"Liberatore, V.: Uniform multipaging reduces to paging. Inf. Process. Lett. 67(1), 9\u201312 (1998)","journal-title":"Inf. Process. Lett."},{"key":"582_CR24","doi-asserted-by":"crossref","unstructured":"Mao, M., Humphrey, M.: Auto-scaling to minimize cost and meet application deadlines in cloud workflows. In: SC (2011)","DOI":"10.1145\/2063384.2063449"},{"key":"582_CR25","doi-asserted-by":"crossref","unstructured":"M\u00f6mke, T., Wiese, A.: A ($$2+\\epsilon $$)-approximation algorithm for the storage allocation problem. In: ICALP, pp. 973\u2013984 (2015)","DOI":"10.1007\/978-3-662-47672-7_79"},{"key":"582_CR26","volume-title":"Optical Networks: A Practical Perspective","author":"R Ramaswami","year":"2009","unstructured":"Ramaswami, R., Sivarajan, K.N., Sasaki, G.H.: Optical Networks: A Practical Perspective. Morgan Kaufmann Publisher Inc., San Francisco (2009)"},{"issue":"2\u20133","key":"582_CR27","first-page":"72","volume":"102","author":"BV Roy","year":"2007","unstructured":"Roy, B.V.: A short proof of optimality for the MIN cache replacement algorithm. Inf. Process. Lett. 102(2\u20133), 72\u201373 (2007)","journal-title":"Inf. Process. Lett."},{"key":"582_CR28","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Hoboken (1998)"},{"issue":"3","key":"582_CR29","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s10951-017-0514-4","volume":"21","author":"H Shachnai","year":"2018","unstructured":"Shachnai, H., Voloshin, A., Zaks, S.: Flexible bandwidth assignment with application to optical networks. J. Scheduling 21(3), 327\u2013336 (2018)","journal-title":"J. Scheduling"},{"key":"582_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jda.2017.07.001","volume":"45","author":"H Shachnai","year":"2017","unstructured":"Shachnai, H., Voloshin, A., Zaks, S.: Optimizing bandwidth allocation in elastic optical networks with application to scheduling. J. Discrete Algorithms 45, 1\u201313 (2017)","journal-title":"J. Discrete Algorithms"},{"key":"582_CR31","doi-asserted-by":"crossref","unstructured":"Shalom, M., Wong, P., Zaks, S.: Profit maximization in flex-grid all-optical networks. In: SIROCCO (2013)","DOI":"10.1007\/978-3-319-03578-9_21"},{"key":"582_CR32","first-page":"1","volume":"69","author":"WT Tutte","year":"1965","unstructured":"Tutte, W.T.: Lectures on matroids. J. Res. Natl. Bur. Stand. (B) 69, 1\u201347 (1965)","journal-title":"J. Res. Natl. Bur. Stand. (B)"},{"issue":"3","key":"582_CR33","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s11107-012-0378-7","volume":"24","author":"L Velasco","year":"2012","unstructured":"Velasco, L., Klinkowski, M., Ruiz, M., Comellas, J.: Modeling the routing and spectrum allocation problem for flexgrid optical networks. Photonic Netw. Commun. 24(3), 177\u2013186 (2012)","journal-title":"Photonic Netw. Commun."},{"key":"582_CR34","unstructured":"Voloshin, A.: Flexible resource allocation for network problems. Ph.D. Thesis, Computer Science Department, Technion (2017)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00582-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00582-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00582-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,5]],"date-time":"2020-05-05T23:11:33Z","timestamp":1588720293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00582-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,7]]},"references-count":34,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["582"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00582-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,7]]},"assertion":[{"value":"18 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}