{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:17Z","timestamp":1750308737431,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Alberta Ingenuity new faculty award"},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            We consider the unsplittable flow problem on a line. In this problem, we are given a set of\n            <jats:italic>n<\/jats:italic>\n            tasks, each specified by a start time\n            <jats:italic>s<\/jats:italic>\n            <jats:sub>i<\/jats:sub>\n            , an end time\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>i<\/jats:sub>\n            , a demand\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            &gt; 0, and a profit\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            &gt; 0. A task, if accepted, requires\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            units of \u201cbandwidth\u201d from time\n            <jats:italic>s<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            to\n            <jats:italic>t<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            and accrues a profit of\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            . For every time\n            <jats:italic>t<\/jats:italic>\n            , we are also specified the available bandwidth\n            <jats:italic>c<\/jats:italic>\n            <jats:sub>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sub>\n            , and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints.\n          <\/jats:p>\n          <jats:p>\n            We present the first polynomial time\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) approximation algorithm for this problem. This significantly advances the state of the art, as no polynomial time\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) approximation was known previously. Previous results for this problem were known only in more restrictive settings; in particular, either the instance satisfies the so-called \u201cno-bottleneck\u201d assumption: max\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            \u2264 min\n            <jats:sub>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>c<\/jats:italic>\n            <jats:sub>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sub>\n            , or the ratio of both maximum to minimum demands and maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in\n            <jats:italic>n<\/jats:italic>\n            . Our result, on the other hand, does not require these assumptions.\n          <\/jats:p>\n          <jats:p>\n            Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an \u03a9(\n            <jats:italic>n<\/jats:italic>\n            ) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.\n          <\/jats:p>","DOI":"10.1145\/2532645","type":"journal-article","created":{"date-parts":[[2014,2,7]],"date-time":"2014-02-07T14:22:52Z","timestamp":1391782972000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A logarithmic approximation for unsplittable flow on line graphs"],"prefix":"10.1145","volume":"10","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Yorktown Heights, NY"}]},{"given":"Zachary","family":"Friggstad","sequence":"additional","affiliation":[{"name":"University of Waterloo, Alberta, Canada"}]},{"given":"Rohit","family":"Khandekar","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Jersey city, NJ, USA"}]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[{"name":"University of Alberta, Edmonton, Alberta, Canada"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.41"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183907.1183910"},{"key":"e_1_2_1_3_1","unstructured":"A. Arackaparambil A. Chakrabarti and C. Huang. 2009. Approximability of unsplittable flow on trees. Dartmouth Technical Report TR2009-642.  A. Arackaparambil A. Chakrabarti and C. Huang. 2009. Approximability of unsplittable flow on trees. Dartmouth Technical Report TR2009-642."},{"volume-title":"Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization. 15--29","author":"Azar Y.","key":"e_1_2_1_4_1","unstructured":"Y. Azar and O. Regev . 2001. Strongly polynomial algorithms for the unsplittable flow problem . In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization. 15--29 . Y. Azar and O. Regev. 2001. Strongly polynomial algorithms for the unsplittable flow problem. In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization. 15--29."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132617"},{"volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909)","author":"Bansal N.","key":"e_1_2_1_6_1","unstructured":"N. Bansal , Z. Friggstad , R. Khandekar , and M. Salavatipour . 2009. A logarithmic approximation for unsplittable flow on line graphs . In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 702--709. N. Bansal, Z. Friggstad, R. Khandekar, and M. Salavatipour. 2009. A logarithmic approximation for unsplittable flow on line graphs. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909). Society for Industrial and Applied Mathematics, Philadelphia, PA, 702--709."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.2.255.12228"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000816"},{"volume-title":"Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u201902)","author":"Chakrabarti A.","key":"e_1_2_1_11_1","unstructured":"A. Chakrabarti , C. Chekuri , A. Kumar , and A. Gupta . 2002. Approximation algorithms for the unsplittable flow problem . In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u201902) . Springer-Verlag, London, 51--66. A. Chakrabarti, C. Chekuri, A. Kumar, and A. Gupta. 2002. Approximation algorithms for the unsplittable flow problem. In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u201902). Springer-Verlag, London, 51--66."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273343"},{"key":"e_1_2_1_15_1","unstructured":"S. Fortune J. Hopcroft and J. Wyllie. 1978. The Directed Subgraph Homeomorphism Problem. Tech. rep. Ithaca NY.   S. Fortune J. Hopcroft and J. Wyllie. 1978. The Directed Subgraph Homeomorphism Problem. Tech. rep. Ithaca NY."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"Frieze A.","year":"2000","unstructured":"A. Frieze . 2000 . Edge-disjoint paths in expander graphs . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 717--725. A. Frieze. 2000. Edge-disjoint paths in expander graphs. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900). Society for Industrial and Applied Mathematics, Philadelphia, PA, 717--725."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"volume-title":"Proceedings of the 37th Annual Symposium on Foundations of Computer Science. IEEE Computer Society","author":"Kleinberg J.","key":"e_1_2_1_21_1","unstructured":"J. Kleinberg and R. Rubinfeld . 1996. Short paths in expander graphs . In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. IEEE Computer Society , Washington, DC, 86. J. Kleinberg and R. Rubinfeld. 1996. Short paths in expander graphs. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Washington, DC, 86."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.006"},{"volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900)","author":"Phillips A.","key":"e_1_2_1_23_1","unstructured":"A. Phillips , R. Uma , and J. Wein . 2000. Off-line admission control for general scheduling problems . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 879--888. A. Phillips, R. Uma, and J. Wein. 2000. Off-line admission control for general scheduling problems. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201900). Society for Industrial and Applied Mathematics, Philadelphia, PA, 879--888."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796366"},{"volume-title":"Approximation Algorithms","author":"Vazirani V.","key":"e_1_2_1_25_1","unstructured":"V. Vazirani . 2003. Approximation Algorithms . Springer . V. Vazirani. 2003. Approximation Algorithms. Springer."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2532645","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2532645","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:05Z","timestamp":1750278125000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2532645"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2532645"],"URL":"https:\/\/doi.org\/10.1145\/2532645","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}