{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T15:09:55Z","timestamp":1745334595234,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s10107-021-01700-8","type":"journal-article","created":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T14:04:07Z","timestamp":1629122647000},"page":"403-419","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Integer plane multiflow maximisation: one-quarter-approximation and gaps"],"prefix":"10.1007","volume":"195","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7923-4464","authenticated-orcid":false,"given":"Naveen","family":"Garg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e1s","family":"Seb\u0151","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,16]]},"reference":[{"key":"1700_CR1","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0012-365X(76)90147-3","volume":"16","author":"K Appel","year":"1976","unstructured":"Appel, K., Haken, W.: A proof of the four color theorem. Discret. Math. 16, 179\u2013180 (1976)","journal-title":"Discret. Math."},{"issue":"1","key":"1700_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994). https:\/\/doi.org\/10.1145\/174644.174650","journal-title":"J. ACM"},{"issue":"4","key":"1700_CR3","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/j.orl.2008.01.009","volume":"36","author":"J Cheriyan","year":"2008","unstructured":"Cheriyan, J., Karloff, H., Khandekar, R., K\u00f6nemann, J.: On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4), 399\u2013401 (2008)","journal-title":"Oper. Res. Lett."},{"key":"1700_CR4","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0167-5060(08)70734-9","volume":"I","author":"J Edmonds","year":"1977","unstructured":"Edmonds, J., Giles, R.: A min-max relation for submodular functions in graphs. Ann. Discret. Math. I, 185\u2013204 (1977)","journal-title":"Ann. Discret. Math."},{"issue":"1","key":"1700_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-006-0063-7","volume":"110","author":"S Fiorini","year":"1995","unstructured":"Fiorini, S., Hardy, N., Reed, B., Vetta, A.: Approximate min-max relations for odd cycles in planar graphs. Math. Program. 110(1), 71\u201391 (1995)","journal-title":"Math. Program."},{"key":"1700_CR6","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford University Press (2011)"},{"key":"1700_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF01585937","volume":"70","author":"A Frank","year":"1995","unstructured":"Frank, A., Szigeti, Z.: A note on packing paths in planar graphs. Math. Program. 70, 201\u2013209 (1995)","journal-title":"Math. Program."},{"key":"1700_CR8","unstructured":"Garg, N., Kumar, N.: Dual half-integrality for uncrossable cut cover and its application to maximum half-integral flow. In: European Symposium on Algorithms (2020)"},{"key":"1700_CR9","doi-asserted-by":"crossref","unstructured":"Garg, N., Kumar, N., Seb\u0151, A.: Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 144\u2013157. Springer (2020)","DOI":"10.1007\/978-3-030-45771-6_12"},{"issue":"2","key":"1700_CR10","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi) cut theorems and their applications. SIAM J. Comput. 25(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1700_CR11","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"},{"key":"1700_CR12","doi-asserted-by":"crossref","unstructured":"Hoffman, A.J., Kruskal J.B.: Integral boundary points of convex polyhedra. Linear Inequal. Relat. Syst., 223\u2013246 (1956)","DOI":"10.1515\/9781400881987-014"},{"key":"1700_CR13","doi-asserted-by":"crossref","unstructured":"Huang, C.C., Mari, M., Mathieu, C., Schewior, K., Vygen, J.: An approximation algorithm for fully planar edge-disjoint paths. arXiv preprint arXiv:2001.01715 (2020)","DOI":"10.1137\/20M1319401"},{"key":"1700_CR14","unstructured":"Huang, C.C., Mari, M., Mathieu, C., Vygen, J.: Approximating maximum integral multiflows on bounded genus graphs. arXiv preprint arXiv:2005.00575 (2020)"},{"key":"1700_CR15","doi-asserted-by":"crossref","unstructured":"Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pp. 682\u2013690. ACM (1993)","DOI":"10.1145\/167088.167261"},{"key":"1700_CR16","unstructured":"Klein, P.N., Mathieu, C., Zhou, H.: Correlation clustering and two-edge-connected augmentation for planar graphs. In: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)"},{"key":"1700_CR17","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF01581198","volume":"55","author":"E Korach","year":"1992","unstructured":"Korach, E., Penn, M.: Tight integral duality gap in the Chinese postman problem. Math. Program. 55, 183\u2013191 (1992)","journal-title":"Math. Program."},{"key":"1700_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"B Korte","year":"2012","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, vol. 21. Springer, Berlin and Heidelberg, collection Algorithms and Combinatorics, fifth edition (2012)"},{"key":"1700_CR19","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0095-8956(03)00078-9","volume":"90","author":"D Kr\u00e1l","year":"2004","unstructured":"Kr\u00e1l, D., Voss, H.: Edge-disjoint odd cycles in planar graphs. J. Combinat. Theory Ser. B 90, 107\u2013120 (2004)","journal-title":"J. Combinat. Theory Ser. B"},{"issue":"2","key":"1700_CR20","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1137\/0215034","volume":"15","author":"K Matsumoto","year":"1986","unstructured":"Matsumoto, K., Nishizeki, T., Saito, N.: Planar multicommodity fows, maximum matchings and negative cycles. SIAM J. Comput. 15(2), 495\u2013510 (1986)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1700_CR21","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01202792","volume":"13","author":"M Middendorf","year":"1993","unstructured":"Middendorf, M., Pfeiffer, F.: On the complexity of the disjoint paths problem. Combinatorica 13(1), 97\u2013107 (1993)","journal-title":"Combinatorica"},{"issue":"1","key":"1700_CR22","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0095-8956(81)80012-3","volume":"31","author":"H Okamura","year":"1981","unstructured":"Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Combinat. Theory Ser. B 31(1), 75\u201381 (1981)","journal-title":"J. Combinat. Theory Ser. B"},{"key":"1700_CR23","doi-asserted-by":"crossref","unstructured":"Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pp. 571\u2013575 (1996)","DOI":"10.1145\/237814.238005"},{"key":"1700_CR24","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley and Chichester (1986)"},{"key":"1700_CR25","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol.\u00a024. Springer (2003)"},{"key":"1700_CR26","doi-asserted-by":"crossref","unstructured":"Seguin-Charbonneau, L., Shepherd, F.B.: Maximum edge-disjoint paths in planar graphs with congestion 2. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 200\u2013209. IEEE (2011)","DOI":"10.1109\/FOCS.2011.30"},{"issue":"1","key":"1700_CR27","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1112\/plms\/s3-42.1.178","volume":"3","author":"PD Seymour","year":"1981","unstructured":"Seymour, P.D.: On odd cuts and plane multicommodity flows. Proc. Lond. Math. Soc. 3(1), 178\u2013192 (1981)","journal-title":"Proc. Lond. Math. Soc."},{"key":"1700_CR28","doi-asserted-by":"publisher","unstructured":"Tardos, \u00c9., Vazirani, V.V.: Improved bounds for the max-flow min-multicut ratio for planar and k\\_r, r-free graphs. Inf. Process. Lett. 47(2), 77\u201380 (1993). https:\/\/doi.org\/10.1016\/0020-0190(93)90228-2","DOI":"10.1016\/0020-0190(93)90228-2"},{"key":"1700_CR29","doi-asserted-by":"crossref","unstructured":"Tutte, W.T.: Lectures on matroids. J. Res. Nat. Bureau Stand. B(69) (1965)","DOI":"10.6028\/jres.069B.001"},{"issue":"3","key":"1700_CR30","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/BF01299747","volume":"15","author":"DP Williamson","year":"1995","unstructured":"Williamson, D.P., Goemans, M.X., Mihail, M., Vazirani, V.V.: A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica 15(3), 435\u2013454 (1995)","journal-title":"Combinatorica"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01700-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01700-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01700-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T15:30:15Z","timestamp":1666366215000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01700-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,16]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1700"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01700-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,8,16]]},"assertion":[{"value":"19 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2021","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 declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}