{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:15:51Z","timestamp":1760015751161,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SPP 1736"],"award-info":[{"award-number":["SPP 1736"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to its destination. Given some flow\u00a0<jats:italic>x<\/jats:italic> that is not necessarily unsplittable but satisfies all demands, it is a natural question to ask for an unsplittable flow\u00a0<jats:italic>y<\/jats:italic> that does not deviate from\u00a0<jats:italic>x<\/jats:italic> by too much, i.e.,\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$y_a\\approx x_a$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>y<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>x<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all arcs\u00a0<jats:italic>a<\/jats:italic>. Twenty years ago, in a landmark paper, Dinitz et al. (Combinatorica 19:17\u201341, 1999) proved that there exists an unsplittable flow\u00a0<jats:italic>y<\/jats:italic> such that\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$y_a\\le x_a+d_{\\max }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>y<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>x<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all arcs\u00a0<jats:italic>a<\/jats:italic>, where\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$d_{\\max }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>max<\/mml:mo>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> denotes the maximum demand value. Our first contribution is a considerably simpler one-page proof for this classical result, based upon an entirely new approach. Secondly, using a subtle variant of this approach, we obtain a new result: There is an unsplittable flow\u00a0<jats:italic>y<\/jats:italic> such that\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$y_a\\ge x_a-d_{\\max }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>y<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>x<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all arcs\u00a0<jats:italic>a<\/jats:italic>. Finally, building upon an iterative rounding technique previously introduced by Kolliopoulos and Stein (SIAM J Comput 31:919\u2013946, 2002) and Skutella (Math Program 91:493\u2013514, 2002), we prove existence of an unsplittable flow that simultaneously satisfies the upper and lower bounds for the special case when demands are integer multiples of each other. For arbitrary demand values, we prove the weaker simultaneous bounds\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$x_a\/2-d_{\\max }\\le y_a\\le 2x_a+d_{\\max }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>x<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>y<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:msub>\n                      <mml:mi>x<\/mml:mi>\n                      <mml:mi>a<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mo>max<\/mml:mo>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all arcs\u00a0<jats:italic>a<\/jats:italic>.\n<\/jats:p>","DOI":"10.1007\/s10107-021-01704-4","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T10:03:20Z","timestamp":1630490600000},"page":"477-496","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Single source unsplittable flows with arc-wise lower and upper bounds"],"prefix":"10.1007","volume":"192","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6119-7885","authenticated-orcid":false,"given":"Sarah","family":"Morell","sequence":"first","affiliation":[]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,1]]},"reference":[{"key":"1704_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall Inc, Upper Saddle River (1993)"},{"key":"1704_CR2","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s00453-005-1167-9","volume":"42","author":"G Baier","year":"2005","unstructured":"Baier, G., K\u00f6hler, E., Skutella, M.: On the $$k$$-splittable flow problem. Algorithmica 42, 231\u2013248 (2005)","journal-title":"Algorithmica"},{"key":"1704_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Kulkarni, J.: Minimizing flow-time on unrelated machines. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pp. 851\u2013860 (2015)","DOI":"10.1145\/2746539.2746601"},{"key":"1704_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s004930050043","volume":"19","author":"Y Dinitz","year":"1999","unstructured":"Dinitz, Y., Garg, N., Goemans, M.X.: On the single source unsplittable flow problem. Combinatorica 19, 17\u201341 (1999)","journal-title":"Combinatorica"},{"issue":"2","key":"1704_CR5","first-page":"3","volume":"10","author":"J Du","year":"2005","unstructured":"Du, J., Kolliopoulos, S.: Implementing approximation algorithms for the single-source unsplittable flow problem. J. Exp. Algorithmics 10(2), 3 (2005)","journal-title":"J. Exp. Algorithmics"},{"key":"1704_CR6","doi-asserted-by":"crossref","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press (1962)","DOI":"10.1515\/9781400875184"},{"key":"1704_CR7","unstructured":"Kleinberg, J.M.: Approximation algorithms for disjoint paths problems. PhD thesis, M.I.T (1996)"},{"key":"1704_CR8","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/s00224-007-9068-8","volume":"43","author":"R Koch","year":"2008","unstructured":"Koch, R., Skutella, M., Spenke, I.: Maximum $$k$$-splittable $$s, t$$-flows. Theory Comput. Syst. 43, 56\u201366 (2008)","journal-title":"Theory Comput. Syst."},{"key":"1704_CR9","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ipl.2004.12.009","volume":"94","author":"SG Kolliopoulos","year":"2005","unstructured":"Kolliopoulos, S.G.: Minimum-cost single-source 2-splittable flow. Inf. Process. Lett. 94, 15\u201318 (2005)","journal-title":"Inf. Process. Lett."},{"key":"1704_CR10","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S.G.: Edge-disjoint paths and unsplittable flow. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall\/CRC (2007)","DOI":"10.1201\/9781420010749.ch57"},{"key":"1704_CR11","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1137\/S0097539799355314","volume":"31","author":"SG Kolliopoulos","year":"2002","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximation algorithms for single-source unsplittable flow. SIAM J. Comput. 31, 919\u2013946 (2002)","journal-title":"SIAM J. Comput."},{"key":"1704_CR12","doi-asserted-by":"crossref","unstructured":"Martens, M., Salazar, F., Skutella, M.: Representing single source multicommodity flows as convex combinations of unsplittable flows. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) Algorithms \u2013 ESA \u201907. Lecture Notes in Computer Science, vol. 4698, pp. 395\u2013406. Springer (2007)","DOI":"10.1007\/978-3-540-75520-3_36"},{"key":"1704_CR13","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37, 130\u2013143 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"1704_CR14","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"1704_CR15","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.orl.2008.12.004","volume":"37","author":"F Salazar","year":"2009","unstructured":"Salazar, F., Skutella, M.: Single-source $$k$$-splittable min-cost flows. Oper. Res. Lett. 37, 71\u201374 (2009)","journal-title":"Oper. Res. Lett."},{"key":"1704_CR16","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s101070100260","volume":"91","author":"M Skutella","year":"2002","unstructured":"Skutella, M.: Approximating the single source unsplittable min-cost flow problem. Math. Program. 91, 493\u2013514 (2002)","journal-title":"Math. Program."},{"key":"1704_CR17","doi-asserted-by":"crossref","unstructured":"Williamson, D.P.: Network Flow Algorithms. Cambridge University Press (2019)","DOI":"10.1017\/9781316888568"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01704-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01704-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01704-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T17:19:49Z","timestamp":1646846389000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01704-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,1]]},"references-count":17,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1704"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01704-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,9,1]]},"assertion":[{"value":"18 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}