{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T23:46:05Z","timestamp":1775000765334,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519959","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"289-302","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A PTAS for unsplittable flow on a path"],"prefix":"10.1145","author":[{"given":"Fabrizio","family":"Grandoni","sequence":"first","affiliation":[{"name":"USI-SUPSI, Switzerland"}]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[{"name":"University of Augsburg, Germany"}]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[{"name":"Vrije Universiteit Amsterdam, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33461-5_28"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.50"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_3"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Aris Anagnostopoulos Fabrizio Grandoni Stefano Leonardi and Andreas Wiese. 2014. A Mazing 2+\u03b5 Approximation for Unsplittable Flow on a Path. In SODA. 26\u201341.  Aris Anagnostopoulos Fabrizio Grandoni Stefano Leonardi and Andreas Wiese. 2014. A Mazing 2+\u03b5 Approximation for Unsplittable Flow on a Path. In SODA. 26\u201341.","DOI":"10.1137\/1.9781611973402.3"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"N. Bansal A. Chakrabarti A. Epstein and B. Schieber. 2006. A quasi-PTAS for unsplittable flow on line graphs. In STOC. ACM 721\u2013729.  N. Bansal A. Chakrabarti A. Epstein and B. Schieber. 2006. A quasi-PTAS for unsplittable flow on line graphs. In STOC. ACM 721\u2013729.","DOI":"10.1145\/1132516.1132617"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"N. Bansal Z. Friggstad R. Khandekar and R. Salavatipour. 2009. A logarithmic approximation for unsplittable flow on line graphs. In SODA. 702\u2013709.  N. Bansal Z. Friggstad R. Khandekar and R. Salavatipour. 2009. A logarithmic approximation for unsplittable flow on line graphs. In SODA. 702\u2013709.","DOI":"10.1137\/1.9781611973068.77"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"A. Bar-Noy R. Bar-Yehuda A. Freund J. Naor and B. Schieber. 2000. A unified approach to approximating resource allocation and scheduling. In STOC. 735\u2013744.  A. Bar-Noy R. Bar-Yehuda A. Freund J. Naor and B. Schieber. 2000. A unified approach to approximating resource allocation and scheduling. In STOC. 735\u2013744.","DOI":"10.1145\/335305.335410"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"R. Bar-Yehuda M. Beder Y. Cohen and D. Rawitz. 2006. Resource Allocation in Bounded Degree Trees. In ESA. 64\u201375.  R. Bar-Yehuda M. Beder Y. Cohen and D. Rawitz. 2006. Resource Allocation in Bounded Degree Trees. In ESA. 64\u201375.","DOI":"10.1007\/11841036_9"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9121-7"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0137-8"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.5"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/120868360"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000816"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Venkatesan T. Chakaravarthy Anamitra R. Choudhury Shalmoli Gupta Sambuddha Roy and Yogish Sabharwal. 2014. Improved Algorithms for Resource Allocation under Varying Capacity. In ESA. 222\u2013234.  Venkatesan T. Chakaravarthy Anamitra R. Choudhury Shalmoli Gupta Sambuddha Roy and Yogish Sabharwal. 2014. Improved Algorithms for Resource Allocation under Varying Capacity. In ESA. 222\u2013234.","DOI":"10.1007\/978-3-662-44777-2_19"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118733.3118817"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Parinya Chalermsook. 2011. Coloring and maximum independent set of rectangles. Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques 123\u2013134.  Parinya Chalermsook. 2011. Coloring and maximum independent set of rectangles. Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques 123\u2013134.","DOI":"10.1007\/978-3-642-22935-0_11"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the 20 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201909)","author":"Chalermsook P.","unstructured":"P. Chalermsook and J. Chuzhoy . 2009. Maximum independent set of rectangles . In Proceedings of the 20 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201909) . SIAM, 892\u2013901. P. Chalermsook and J. Chuzhoy. 2009. Maximum independent set of rectangles. In Proceedings of the 20 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201909). SIAM, 892\u2013901."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"C. Chekuri A. Ene and N. Korula. 2009. Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. In APPROX-RANDOM. 42\u201355.  C. Chekuri A. Ene and N. Korula. 2009. Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. In APPROX-RANDOM. 42\u201355.","DOI":"10.1007\/978-3-642-03685-9_4"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"C. Chekuri M. Mydlarz and F. Shepherd. 2007. Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms 3 (2007).  C. Chekuri M. Mydlarz and F. Shepherd. 2007. Multicommodity demand flow in a tree and packing integer programs. ACM Transactions on Algorithms 3 (2007).","DOI":"10.1145\/1273340.1273343"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/07408170208928886"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"M. Chrobak G. Woeginger K. Makino and H. Xu. 2010. Caching Is Hard Even in the Fault Model. In ESA. 195\u2013206.  M. Chrobak G. Woeginger K. Makino and H. Xu. 2010. Caching Is Hard Even in the Fault Model. In ESA. 195\u2013206.","DOI":"10.1007\/978-3-642-15775-2_17"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.92"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.028"},{"key":"e_1_3_2_1_24_1","volume-title":"APPROX-RANDOM (LIPIcs","volume":"283","author":"Friggstad Zachary","year":"2015","unstructured":"Zachary Friggstad and Zhihan Gao . 2015 . On Linear Programming Relaxations for Unsplittable Flow in Trees . In APPROX-RANDOM (LIPIcs , Vol. 40). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 265\u2013 283 . Zachary Friggstad and Zhihan Gao. 2015. On Linear Programming Relaxations for Unsplittable Flow in Trees. In APPROX-RANDOM (LIPIcs, Vol. 40). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 265\u2013283."},{"key":"e_1_3_2_1_25_1","volume-title":"Madhusudhan Reddy Pittu, and Andreas Wiese","author":"G\u00e1lvez Waldo","year":"2021","unstructured":"Waldo G\u00e1lvez , Arindam Khan , Mathieu Mari , Tobias M\u00f6mke , Madhusudhan Reddy Pittu, and Andreas Wiese . 2021 . A (2+\u220a )-Approximation Algorithm for Maximum Independent Set of Rectangles. CoRR , abs\/2106.00623 (2021), arXiv:2106.00623. arxiv:2106.00623 Waldo G\u00e1lvez, Arindam Khan, Mathieu Mari, Tobias M\u00f6mke, Madhusudhan Reddy Pittu, and Andreas Wiese. 2021. A (2+\u220a )-Approximation Algorithm for Maximum Independent Set of Rectangles. CoRR, abs\/2106.00623 (2021), arXiv:2106.00623. arxiv:2106.00623"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Fabrizio Grandoni Salvatore Ingala and Sumedha Uniyal. 2015. Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows. In WAOA. 13\u201324.  Fabrizio Grandoni Salvatore Ingala and Sumedha Uniyal. 2015. Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows. In WAOA. 13\u201324.","DOI":"10.1007\/978-3-319-28684-6_2"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.49"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Fabrizio Grandoni Tobias M\u00f6mke and Andreas Wiese. 2022. Unsplittable Flow on a Path: The Game!. In SODA.  Fabrizio Grandoni Tobias M\u00f6mke and Andreas Wiese. 2022. Unsplittable Flow on a Path: The Game!. In SODA.","DOI":"10.1137\/1.9781611977073.39"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Fabrizio Grandoni Tobias M\u00f6mke Andreas Wiese and Hang Zhou. 2017. To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack. In SODA. 2411\u20132422.  Fabrizio Grandoni Tobias M\u00f6mke Andreas Wiese and Hang Zhou. 2017. To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack. In SODA. 2411\u20132422.","DOI":"10.1137\/1.9781611974782.159"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188894"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/140998846"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.54"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"S. Leonardi A. Marchetti-Spaccamela and A. Vitaletti. 2000. Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints. In FSTTCS. 409\u2013420.  S. Leonardi A. Marchetti-Spaccamela and A. Vitaletti. 2000. Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints. In FSTTCS. 409\u2013420.","DOI":"10.1007\/3-540-44450-5_33"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.67"},{"key":"e_1_3_2_1_35_1","volume-title":"Approximating Maximum Independent Set for Rectangles in the Plane. CoRR, abs\/2101.00326","author":"Mitchell Joseph S. B.","year":"2021","unstructured":"Joseph S. B. Mitchell . 2021. Approximating Maximum Independent Set for Rectangles in the Plane. CoRR, abs\/2101.00326 ( 2021 ), arXiv:2101.00326. arxiv:2101.00326 Joseph S. B. Mitchell. 2021. Approximating Maximum Independent Set for Rectangles in the Plane. CoRR, abs\/2101.00326 (2021), arXiv:2101.00326. arxiv:2101.00326"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_79"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.86"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 11 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201900)","author":"Phillips C. A.","unstructured":"C. A. Phillips , R. N. Uma , and J. Wein . 2000. Off-line admission control for general scheduling problems . In Proceedings of the 11 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201900) . ACM, 879\u2013888. C. A. Phillips, R. N. Uma, and J. Wein. 2000. Off-line admission control for general scheduling problems. In Proceedings of the 11 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201900). ACM, 879\u2013888."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.67"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519959","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519959","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:38Z","timestamp":1750268978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519959"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":39,"alternative-id":["10.1145\/3519935.3519959","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519959","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}