{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T23:46:01Z","timestamp":1775000761861,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Lise Meitner Award Fellowship"},{"name":"SNSF","award":["APXNET 200021_159697 \/ 1"],"award-info":[{"award-number":["APXNET 200021_159697 \/ 1"]}]},{"name":"European Research Council (ERC)","award":["Starting Grant NEWNET 279352"],"award-info":[{"award-number":["Starting Grant NEWNET 279352"]}]},{"name":"German Research Foundation (DFG)","award":["MO 2889\/1-1"],"award-info":[{"award-number":["MO 2889\/1-1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188894","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"607-619","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A (5\/3 + \u03b5)-approximation for unsplittable flow on a path: placing small tasks into boxes"],"prefix":"10.1145","author":[{"given":"Fabrizio","family":"Grandoni","sequence":"first","affiliation":[{"name":"University of Lugano, Switzerland"}]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[{"name":"University of Bremen, Germany \/ Saarland University, Germany"}]},{"given":"Andreas","family":"Wiese","sequence":"additional","affiliation":[{"name":"University of Chile, Chile"}]},{"given":"Hang","family":"Zhou","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique, France"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Anna Adamaszek Parinya Chalermsook Alina Ene and Andreas Wiese. 2016.  Anna Adamaszek Parinya Chalermsook Alina Ene and Andreas Wiese. 2016."},{"key":"e_1_3_2_2_2_1","volume-title":"IPCO (Lecture Notes in Computer Science)","author":"Trees Submodular Unsplittable","unstructured":"Submodular Unsplittable Flow on Trees . In IPCO (Lecture Notes in Computer Science) , Vol. 9682 . 337\u2013349. 3- 319- 33461- 5_28 Submodular Unsplittable Flow on Trees. In IPCO (Lecture Notes in Computer Science), Vol. 9682. 337\u2013349. 3- 319- 33461- 5_28"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_3"},{"key":"e_1_3_2_2_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_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90037-0"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132617"},{"key":"e_1_3_2_2_7_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_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335410"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_9"},{"key":"e_1_3_2_2_10_1","unstructured":"Jatin Batra Naveen Garg Amit Kumar Tobias M\u00f6mke and Andreas Wiese. 2015.  Jatin Batra Naveen Garg Amit Kumar Tobias M\u00f6mke and Andreas Wiese. 2015."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/120868360"},{"key":"e_1_3_2_2_12_1","article-title":"An improved approximation algorithm for resource allocation","volume":"48","author":"C\u0103linescu Gruia","year":"2011","unstructured":"Gruia C\u0103linescu , Amit Chakrabarti , Howard J. Karloff , and Yuval Rabani . 2011 . An improved approximation algorithm for resource allocation . ACM Transactions on Algorithms 7, Article 48 (2011), 48:1\u201348:7 pages. Gruia C\u0103linescu, Amit Chakrabarti, Howard J. Karloff, and Yuval Rabani. 2011. An improved approximation algorithm for resource allocation. ACM Transactions on Algorithms 7, Article 48 (2011), 48:1\u201348:7 pages.","journal-title":"ACM Transactions on Algorithms 7, Article"},{"key":"e_1_3_2_2_13_1","unstructured":"2000816  2000816"},{"key":"e_1_3_2_2_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_2_15_1","unstructured":"A. Chakrabarti C. Chekuri A. Gupta and A. Kumar. 2007.  A. Chakrabarti C. Chekuri A. Gupta and A. Kumar. 2007."},{"key":"e_1_3_2_2_16_1","volume-title":"53\u201378","author":"Unsplittable Flow Problem Approximation Algorithms","year":"2007","unstructured":"Approximation Algorithms for the Unsplittable Flow Problem . Algorithmica 47 ( 2007 ), 53\u201378 . Approximation Algorithms for the Unsplittable Flow Problem. Algorithmica 47 (2007), 53\u201378."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_4"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273343"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/07408170208928886"},{"key":"e_1_3_2_2_20_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_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.028"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_3_2_2_23_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_2_24_1","unstructured":"Fabrizio Grandoni Tobias M\u00f6mke Andreas Wiese and Hang Zhou. 2017.  Fabrizio Grandoni Tobias M\u00f6mke Andreas Wiese and Hang Zhou. 2017."},{"key":"e_1_3_2_2_25_1","unstructured":"To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack. In SODA. 2411\u20132422.   To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack. In SODA. 2411\u20132422."},{"key":"e_1_3_2_2_26_1","unstructured":"S. Leonardi A. Marchetti-Spaccamela and A. Vitaletti. 2000.  S. Leonardi A. Marchetti-Spaccamela and A. Vitaletti. 2000."},{"key":"e_1_3_2_2_27_1","unstructured":"Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints. In FSTTCS. 409\u2013420.  Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints. In FSTTCS. 409\u2013420."},{"key":"e_1_3_2_2_28_1","unstructured":"C. A. Phillips R. N. Uma and J. Wein. 2000. Off-line admission control for general scheduling problems. In SODA. 879\u2013888.   C. A. Phillips R. N. Uma and J. Wein. 2000. Off-line admission control for general scheduling problems. In SODA. 879\u2013888."},{"key":"e_1_3_2_2_29_1","unstructured":"A. Schrijver. 2003.  A. Schrijver. 2003."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188894","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188894","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:10Z","timestamp":1750212430000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188894"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":29,"alternative-id":["10.1145\/3188745.3188894","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188894","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}