{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004889,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":84,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CCF-2330255, CCF1844855, CCF-1955039"],"award-info":[{"award-number":["CCF-2330255, CCF1844855, CCF-1955039"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718267","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"2203-2212","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2585-6027","authenticated-orcid":false,"given":"Li","family":"Chen","sequence":"first","affiliation":[{"name":"Independent, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9864-2406","authenticated-orcid":false,"given":"Andrei","family":"Graur","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2675-7610","authenticated-orcid":false,"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.86"},{"key":"e_1_3_2_1_2_1","unstructured":"Deeksha Adil Rasmus Kyng Richard Peng and Sushant Sachdeva. 2022. Fast Algorithms for \u2113 _p-Regression. arXiv preprint arXiv:2211.03963."},{"key":"e_1_3_2_1_3_1","volume-title":"provably convergent IRLS algorithm for p-norm linear regression. Advances in Neural Information Processing Systems (NeurIPS), 32","author":"Adil Deeksha","year":"2019","unstructured":"Deeksha Adil, Richard Peng, and Sushant Sachdeva. 2019. Fast, provably convergent IRLS algorithm for p-norm linear regression. Advances in Neural Information Processing Systems (NeurIPS), 32 (2019)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.54"},{"volume-title":"Network flows","author":"Ahuja Ravindra K","key":"e_1_3_2_1_5_1","unstructured":"Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. 1988. Network flows. Cambridge, Mass.: Alfred P. Sloan School of Management, Massachusetts \u2026."},{"key":"e_1_3_2_1_6_1","volume-title":"The multiplicative weights update method: a meta-algorithm and applications. Theory of computing, 8, 1","author":"Arora Sanjeev","year":"2012","unstructured":"Sanjeev Arora, Elad Hazan, and Satyen Kale. 2012. The multiplicative weights update method: a meta-algorithm and applications. Theory of computing, 8, 1 (2012), 121\u2013164."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.29"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00018"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780599"},{"key":"e_1_3_2_1_10_1","first-page":"2354","article-title":"Multicommodity Flow Problems","volume":"14","author":"Barnhart Cynthia","year":"2009","unstructured":"Cynthia Barnhart, Niranjan Krishnan, and Pamela H Vance. 2009. Multicommodity Flow Problems.. Encyclopedia of Optimization, 14 (2009), 2354\u20132362.","journal-title":"Encyclopedia of Optimization"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (STOC). 146\u2013155","author":"Bienstock Daniel","year":"2004","unstructured":"Daniel Bienstock and Garud Iyengar. 2004. Solving fractional packing problems in \"0365O(1\/\u03b5 ) iterations. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (STOC). 146\u2013155."},{"key":"e_1_3_2_1_12_1","volume-title":"Faster width-dependent algorithm for mixed packing and covering LPs. Advances in Neural Information Processing Systems, 32","author":"Boob Digvijay","year":"2019","unstructured":"Digvijay Boob, Saurabh Sawlani, and Di Wang. 2019. Faster width-dependent algorithm for mixed packing and covering LPs. Advances in Neural Information Processing Systems, 32 (2019)."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Jan van den Brand and Daniel Zhang. 2023. Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques. arXiv preprint arXiv:2304.12992.","DOI":"10.1109\/FOCS57990.2023.00036"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 1130\u20131137","author":"Bubeck S\u00e9bastien","year":"2018","unstructured":"S\u00e9bastien Bubeck, Michael B Cohen, Yin Tat Lee, and Yuanzhi Li. 2018. An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 1130\u20131137."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Li Chen Andrei Graur and Aaron Sidford. 2025. Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs. arXiv preprint arxiv.org\/abs\/2503.24373.","DOI":"10.1145\/3717823.3718267"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977585.ch5"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3610940"},{"key":"e_1_3_2_1_19_1","unstructured":"Li Chen and Mingquan Ye. 2023. High-accuracy multicommodity flows via iterative refinement. arXiv preprint arXiv:2304.11252."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451025"},{"key":"e_1_3_2_1_22_1","volume-title":"International Conference on Machine Learning (ICML). 1262\u20131271","author":"Clarkson Kenneth","year":"2019","unstructured":"Kenneth Clarkson, Ruosong Wang, and David Woodruff. 2019. Dimensionality reduction for tukey regression. In International Conference on Machine Learning (ICML). 1262\u20131271."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/140963698"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3019134"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316303"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3424305"},{"key":"e_1_3_2_1_27_1","unstructured":"Michael B Cohen Aaron Sidford and Kevin Tian. 2020. Relative lipschitzness in extragradient methods and a direct recipe for acceleration. arXiv preprint arXiv:2011.06572."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/070696507"},{"key":"e_1_3_2_1_30_1","volume-title":"49th International Colloquium on Automata, Languages, and Programming (ICALP). 54:1\u201354:19","author":"Ding Ming","year":"2022","unstructured":"Ming Ding, Rasmus Kyng, and Peng Zhang. 2022. Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP). 54:1\u201354:19."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446232"},{"key":"e_1_3_2_1_33_1","unstructured":"Mehrdad Ghadiri Richard Peng and Santosh S Vempala. 2021. Faster p-Norm Regression Using Sparsity. arXiv preprint arXiv:2109.11537."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087827"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90032-Q"},{"key":"e_1_3_2_1_36_1","unstructured":"Nick Gravin Yuval Peres and Balasubramanian Sivan. 2016. Tight lower bounds for multiplicative weights algorithmic families. arXiv preprint arXiv:1607.02834."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0804004"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592195"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649689"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585202"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322100"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00119"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519971"},{"key":"e_1_3_2_1_44_1","volume-title":"A direct \"0365O(1\/epsilon) iteration parallel algorithm for optimal transport. Advances in Neural Information Processing Systems, 32","author":"Jambulapati Arun","year":"2019","unstructured":"Arun Jambulapati, Aaron Sidford, and Kevin Tian. 2019. A direct \"0365O(1\/epsilon) iteration parallel algorithm for optimal transport. Advances in Neural Information Processing Systems, 32 (2019)."},{"key":"e_1_3_2_1_45_1","unstructured":"Arun Jambulapati and Kevin Tian. 2023. Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations. arXiv preprint arXiv:2303.15627."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545402"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225073"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00020"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634090"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213979"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.2.209"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90061-0"},{"key":"e_1_3_2_1_54_1","unstructured":"Rohit Khandekar Subhash Khot Lorenzo Orecchia and Nisheeth K Vishnoi. 2007. On a cut-matching game for the sparsest cut problem. Univ. California Berkeley CA USA Tech. Rep. UCB\/EECS-2007-177 6 7 (2007) 12."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538903"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792241175"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316410"},{"key":"e_1_3_2_1_58_1","volume-title":"Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, 230\u2013249","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee and Aaron Sidford. 2015. Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, 230\u2013249."},{"key":"e_1_3_2_1_59_1","unstructured":"Yin Tat Lee and Aaron Sidford. 2019. Solving linear programs with Sqrt(rank) linear system solves. arXiv preprint arXiv:1910.08033."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103425"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.68"},{"key":"e_1_3_2_1_62_1","unstructured":"Jason Li and Thatchaphol Saranurak. 2025. Local Sherman\u2019s Algorithm for Multi-commodity Flow. arXiv preprint arXiv:2501.10632."},{"key":"e_1_3_2_1_63_1","volume-title":"International Conference on Machine Learning. 21101\u201321126","author":"Lin Cheuk Yin","year":"2023","unstructured":"Cheuk Yin Lin, Chaobing Song, and Jelena Diakonikolas. 2023. Accelerated cyclic coordinate dual averaging with extrapolation for composite convex optimization. In International Conference on Machine Learning. 21101\u201321126."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384247"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806708"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_3_2_1_68_1","volume-title":"International Conference on Machine Learning (ICML). 888\u2013896","author":"Meng Xiangrui","year":"2013","unstructured":"Xiangrui Meng and Michael Mahoney. 2013. Robust regression on mapreduce. In International Conference on Machine Learning (ICML). 888\u2013896."},{"key":"e_1_3_2_1_69_1","volume-title":"Proceeding of the 20th International Symposium of Mathematical Programming (ISMP).","author":"Nesterov Yurii","year":"2009","unstructured":"Yurii Nesterov. 2009. Fast gradient methods for network flow problems. In Proceeding of the 20th International Symposium of Mathematical Programming (ISMP)."},{"key":"e_1_3_2_1_70_1","volume-title":"A survey of algorithms for convex multicommodity flow problems. Management science, 46, 1","author":"Ouorou Adamou","year":"2000","unstructured":"Adamou Ouorou, Philippe Mahey, and J-Ph Vial. 2000. A survey of algorithms for convex multicommodity flow problems. Management science, 46, 1 (2000), 126\u2013147."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch130"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/3219302.3219303"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614505"},{"key":"e_1_3_2_1_74_1","volume-title":"A polynomial-time algorithm, based on Newton\u2019s method, for linear programming. Mathematical programming, 40, 1-3","author":"Renegar James","year":"1988","unstructured":"James Renegar. 1988. A polynomial-time algorithm, based on Newton\u2019s method, for linear programming. Mathematical programming, 40, 1-3 (1988), 59\u201393."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77620"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055501"},{"key":"e_1_3_2_1_77_1","unstructured":"David B Shmoys. 1997. Cut problems and their application to divide-and-conquer. Approximation algorithms for NP-hard problems 192\u2013235."},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M1470104"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00037"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451108"},{"key":"e_1_3_2_1_82_1","first-page":"145","article-title":"Multicommodity Network Flows: A Survey, Part I: Applications and Formulations","volume":"15","author":"Wang Lin","year":"2018","unstructured":"I-Lin Wang. 2018. Multicommodity Network Flows: A Survey, Part I: Applications and Formulations. International Journal of Operations Research, 15, 4 (2018), 145\u2013153.","journal-title":"International Journal of Operations Research"},{"key":"e_1_3_2_1_83_1","volume-title":"Conference on Learning Theory (COLT). 546\u2013567","author":"Woodruff David","year":"2013","unstructured":"David Woodruff and Qin Zhang. 2013. Subspace embeddings and \u2113 _p-regression using exponential random variables. In Conference on Learning Theory (COLT). 546\u2013567."},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313689"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718267","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:47:20Z","timestamp":1750693640000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718267"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":84,"alternative-id":["10.1145\/3717823.3718267","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718267","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}