{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:41:48Z","timestamp":1781077308404,"version":"3.54.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031931116","type":"print"},{"value":"9783031931123","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-93112-3_3","type":"book-chapter","created":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T04:56:05Z","timestamp":1749531365000},"page":"29-42","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the\u00a0Approximability of\u00a0Unsplittable Flow on\u00a0a\u00a0Path with\u00a0Time Windows"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-6826-398X","authenticated-orcid":false,"given":"Alexander","family":"Armbruster","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9676-4931","authenticated-orcid":false,"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6708-5112","authenticated-orcid":false,"given":"Edin","family":"Husi\u0107","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7321-5457","authenticated-orcid":false,"given":"Antoine","family":"Tinguely","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3705-016X","authenticated-orcid":false,"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,6,4]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing 2+$$\\varepsilon $$ approximation for unsplittable flow on a path. In: SODA, pp. 26\u201341 (2014)","DOI":"10.1137\/1.9781611973402.3"},{"key":"3_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"},{"key":"3_CR3","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":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput. 31(2), 331\u2013352 (2001). https:\/\/doi.org\/10.1137\/S0097539799354138","journal-title":"SIAM J. Comput."},{"issue":"5","key":"3_CR5","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. J. ACM (JACM) 48(5), 1069\u20131090 (2001)","journal-title":"J. ACM (JACM)"},{"key":"3_CR6","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/1.9781611973730.5","DOI":"10.1137\/1.9781611973730.5"},{"issue":"3","key":"3_CR7","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/A:1009822211065","volume":"4","author":"P Berman","year":"2000","unstructured":"Berman, P., DasGupta, B.: Multi-phase algorithms for throughput maximization for real-time scheduling. J. Comb. Optim. 4(3), 307\u2013323 (2000). https:\/\/doi.org\/10.1023\/A:1009822211065","journal-title":"J. Comb. Optim."},{"key":"3_CR8","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 J. Comput. 43, 767\u2013799 (2014)","journal-title":"SIAM J. Comput."},{"key":"3_CR9","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":"3_CR10","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.tcs.2005.11.029","volume":"354","author":"M Chleb\u00edk","year":"2006","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354(3), 320\u2013338 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2005.11.029","journal-title":"Theor. Comput. Sci."},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Woeginger, G., Makino, K., Xu, H.: Caching is hard, even in the fault model. In: ESA, pp. 195\u2013206 (2010)","DOI":"10.1007\/978-3-642-15775-2_17"},{"issue":"4","key":"3_CR12","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1287\/MOOR.1060.0218","volume":"31","author":"J Chuzhoy","year":"2006","unstructured":"Chuzhoy, J., Ostrovsky, R., Rabani, Y.: Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res. 31(4), 730\u2013738 (2006). https:\/\/doi.org\/10.1287\/MOOR.1060.0218","journal-title":"Math. Oper. Res."},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Ingala, S., Uniyal, S.: Improved approximation algorithms for unsplittable flow on a path with time windows. In: WAOA, pp. 13\u201324 (2015)","DOI":"10.1007\/978-3-319-28684-6_2"},{"key":"3_CR14","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A.: Faster (1+$$\\epsilon $$)-approximation for unsplittable flow on a path via resource augmentation and back. In: ESA, vol.\u00a0204, pp. 49:1\u201349:15 (2021)"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A.: A PTAS for unsplittable flow on a path. In: STOC, pp. 289\u2013302. ACM (2022)","DOI":"10.1145\/3519935.3519959"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A.: Unsplittable flow on a path: The game! In: SODA, pp. 906\u2013926. SIAM (2022)","DOI":"10.1137\/1.9781611977073.39"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Grandoni, F., M\u00f6mke, T., Wiese, A., Zhou, H.: To augment or not to augment: solving unsplittable flow on a path by creating slack. In: SODA, pp. 2411\u20132422 (2017)","DOI":"10.1137\/1.9781611974782.159"},{"key":"3_CR18","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"},{"issue":"3","key":"3_CR19","doi-asserted-by":"publisher","first-page":"1649","DOI":"10.1137\/17M1148438","volume":"34","author":"S Im","year":"2020","unstructured":"Im, S., Li, S., Moseley, B.: Breaking 1\u20131\/e barrier for nonpreemptive throughput maximization. SIAM J. Discret. Math. 34(3), 1649\u20131669 (2020). https:\/\/doi.org\/10.1137\/17M1148438","journal-title":"SIAM J. Discret. Math."},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y","volume":"2","author":"F Spieksma","year":"1999","unstructured":"Spieksma, F.: On the approximability of an interval scheduling problem. J. Sched. 2, 215\u2013227 (1999)","journal-title":"J. Sched."},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"WF de la Vega","year":"1981","unstructured":"de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within $$1 + \\varepsilon $$ in linear time. Combinatorica 1, 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511921735"},{"issue":"6","key":"3_CR23","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0020-0190(97)00179-8","volume":"64","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger, G.J.: There is no asymptotic PTAS for two-dimensional vector packing. Inf. Process. Lett. 64(6), 293\u2013297 (1997). https:\/\/doi.org\/10.1016\/S0020-0190(97)00179-8","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-93112-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T10:53:13Z","timestamp":1760007193000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-93112-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031931116","9783031931123"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-93112-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"4 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Baltimore, MD","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ipco25.cs.jhu.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}