{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T03:17:53Z","timestamp":1792034273120,"version":"4.4.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422715"],"award-info":[{"award-number":["CCF-1422715"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s00453-022-01043-6","type":"journal-article","created":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T07:11:37Z","timestamp":1664608297000},"page":"563-583","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved Algorithms for Scheduling Unsplittable Flows on Paths"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2690-406X","authenticated-orcid":false,"given":"Hamidreza","family":"Jahanjou","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erez","family":"Kantor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,10,1]]},"reference":[{"key":"1043_CR1","first-page":"1","volume-title":"Approximation and Online Algorithms","author":"U Adamy","year":"2004","unstructured":"Adamy, U., Erlebach, T.: Online coloring of intervals with bandwidth. In: Solis-Oba, R., Jansen, K. (eds.) Approximation and Online Algorithms, pp. 1\u201312. Springer, Berlin (2004)"},{"key":"1043_CR2","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing 2+eps approximation for unsplittable flow on a path. CoRR arXiv:1211.2670 (2012)","DOI":"10.1137\/1.9781611973402.3"},{"issue":"1","key":"1043_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"EM Arkin","year":"1987","unstructured":"Arkin, E.M., Silverberg, E.B.: Scheduling jobs with fixed start and end times. Discrete Appl. Math. 18(1), 1\u20138 (1987)","journal-title":"Discrete Appl. Math."},{"key":"1043_CR4","doi-asserted-by":"publisher","first-page":"181","DOI":"10.7146\/math.scand.a-10607","volume":"8","author":"E Asplund","year":"1960","unstructured":"Asplund, E., Gr\u00fcnbaum, B.: On a coloring problem. Math. Scand. 8, 181\u2013188 (1960)","journal-title":"Math. Scand."},{"key":"1043_CR5","unstructured":"Aumann, Y., Rabani, Y.: Improved bounds for all optical routing. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201995, pp. 567\u2013576. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1995)"},{"issue":"1","key":"1043_CR6","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tcs.2006.06.014","volume":"363","author":"Y Azar","year":"2006","unstructured":"Azar, Y., Fiat, A., Levy, M., Narayanaswamy, N.: An improved algorithm for online coloring of intervals with bandwidth. Theor. Comput. Sci. 363(1), 18\u201327 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"1043_CR7","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: STOC\u201906, pp. 721\u2013729 (2006)","DOI":"10.1145\/1132516.1132617"},{"key":"1043_CR8","doi-asserted-by":"crossref","unstructured":"Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, M.R.: A logarithmic approximation for unsplittable flow on line graphs. In: SODA\u201909, pp. 702\u2013709 (2009)","DOI":"10.1137\/1.9781611973068.77"},{"issue":"5","key":"1043_CR9","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 48(5), 1069\u20131090 (2001)","journal-title":"J. ACM"},{"key":"1043_CR10","doi-asserted-by":"crossref","unstructured":"Bartlett, M., Frisch, A.M., Hamadi, Y., Miguel, I., Tarim, S.A., Unsworth, C.: The temporal knapsack problem and its solution. In: CPAIOR\u201905, pp. 34\u201348. Springer, Berlin (2005)","DOI":"10.1007\/11493853_5"},{"key":"1043_CR11","doi-asserted-by":"crossref","unstructured":"Bonsma, P., Schulz, J., Wiese, A.: A constant factor approximation algorithm for unsplittable flow on paths. In: FOCS\u201911, pp. 47\u201356 (2011)","DOI":"10.1109\/FOCS.2011.10"},{"issue":"4","key":"1043_CR12","doi-asserted-by":"publisher","first-page":"48:1","DOI":"10.1145\/2000807.2000816","volume":"7","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chakrabarti, A., Karloff, H., Rabani, Y.: An improved approximation algorithm for resource allocation. ACM Trans. Algorithms 7(4), 48:1-48:7 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"1043_CR13","doi-asserted-by":"crossref","unstructured":"Chalermsook, P.: Coloring and maximum independent set of rectangles. In: APPROX. RANDOM 2011. Lecture Notes in Computer Science, vol. 6845. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22935-0_11"},{"key":"1043_CR14","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. Lecture Notes in Computer Science, vol. 2719. Springer, Berlin","DOI":"10.1007\/3-540-45061-0_34"},{"issue":"49","key":"1043_CR15","doi-asserted-by":"publisher","first-page":"4217","DOI":"10.1016\/j.tcs.2010.08.028","volume":"411","author":"A Darmann","year":"2010","unstructured":"Darmann, A., Pferschy, U., Schauer, J.: Resource allocation with time intervals. Theoret. Comput. Sci. 411(49), 4217\u20134234 (2010)","journal-title":"Theoret. Comput. Sci."},{"key":"1043_CR16","unstructured":"Elbassioni, K.M., Garg, N., Gupta, D., Kumar, A., Narula, V., Pal, A.: Approximation algorithms for the unsplittable flow problem on paths and trees. In: FSTTCS\u201912, pp. 267\u2013275 (2012)"},{"issue":"2","key":"1043_CR17","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1137\/070682496","volume":"23","author":"L Epstein","year":"2009","unstructured":"Epstein, L., Erlebach, T., Levin, A.: Online capacitated interval coloring. SIAM J. Discrete Math. 23(2), 822\u2013841 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"1043_CR18","doi-asserted-by":"crossref","unstructured":"Epstein, L., Levy, M.: Online interval coloring and variants. In: ICALP 2005. Lecture Notes in Computer Science, vol. 3580. Springer, Berlin","DOI":"10.1007\/11523468_49"},{"issue":"1","key":"1043_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"issue":"3","key":"1043_CR20","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1002\/net.20305","volume":"54","author":"MC Golumbic","year":"2009","unstructured":"Golumbic, M.C., Lipshteyn, M., Stern, M.: Edge intersection graphs of single bend paths on a grid. Networks 54(3), 130\u2013138 (2009). https:\/\/doi.org\/10.1002\/net.20305","journal-title":"Networks"},{"issue":"4","key":"1043_CR21","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 J. Discrete Math. 1(4), 526\u2013530 (1988)","journal-title":"SIAM J. Discrete Math."},{"key":"1043_CR22","first-page":"143","volume":"33","author":"HA Kierstead","year":"1981","unstructured":"Kierstead, H.A., Trotter, W.T.: An extremal problem in recursive combinatorics. Congr. Numer. 33, 143\u2013153 (1981)","journal-title":"Congr. Numer."},{"key":"1043_CR23","doi-asserted-by":"crossref","unstructured":"Kostochka, A.: Coloring intersection graphs of geometric figures with a given clique number. In: Contemporary Mathematics, vol. 342. AMS (2004)","DOI":"10.1090\/conm\/342\/06137"},{"issue":"6","key":"1043_CR24","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0020-0190(97)00077-X","volume":"62","author":"SR Kumar","year":"1997","unstructured":"Kumar, S.R., Panigrahy, R., Russell, A., Sundaram, R.: A note on optical routing on trees. Inf. Process. Lett. 62(6), 295\u2013300 (1997)","journal-title":"Inf. Process. Lett."},{"key":"1043_CR25","doi-asserted-by":"crossref","unstructured":"Mihail, M., Kaklamanis, C., Rao, S.: Efficient access to optical bandwidth wavelength routing on directed fiber trees, rings, and trees of rings. In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 548\u2013557 (1995)","DOI":"10.1109\/SFCS.1995.492585"},{"key":"1043_CR26","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1002\/1099-1425(200011\/12)3:6<365::AID-JOS56>3.0.CO;2-P","volume":"3","author":"CA Phillips","year":"2000","unstructured":"Phillips, C.A., Uma, R.N., Wein, J.: Off-line admission control for general scheduling problems. J. Sched. 3, 879\u2013888 (2000)","journal-title":"J. Sched."},{"key":"1043_CR27","doi-asserted-by":"crossref","unstructured":"Raghavan, P., Upfal, E.: Efficient routing in all-optical networks. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC \u201994, pp. 134\u2013143. ACM, New York, NY, USA (1994)","DOI":"10.1145\/195058.195119"},{"issue":"6","key":"1043_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(6), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01043-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01043-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01043-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T02:27:45Z","timestamp":1728095265000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01043-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,1]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1043"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01043-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,1]]},"assertion":[{"value":"21 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}