Direct Product Multicommodity Max-Concurrent-Flow Min-Sparse-Cut Theorem

doi:10.1007/s40305-024-00567-8

Journal of the Operations Research Society of China ›› 2026, Vol. 14 ›› Issue (2): 719-729.doi: 10.1007/s40305-024-00567-8

Previous Articles Next Articles

Direct Product Multicommodity Max-Concurrent-Flow Min-Sparse-Cut Theorem

Rui Guan^1,2, Dong-Yue Liang², Wei Wang³, Wei-Hua Yang²

1 School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China;
2 Department of Mathematics, Taiyuan University of Technology, Taiyuan 030024, Shanxi, China;
3 School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an 710049, Shaanxi, China

Received:2023-09-03 Revised:2024-09-02 Online:2026-06-30 Published:2026-07-06
Contact: Dong-Yue Liang E-mail:liangdongyue@tyut.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (No.12371356), Major Research Project of Shanxi Province (No.202202020101006).

Abstract

Abstract: We extend the max-concurrent-flow min-sparse-cut theorem from product multicommodity to direct product multicommodity. We prove that $\Theta(\log k)$ is the tight gap between the max-concurrent-flow and the min-sparse-cut for direct product multicommodity, where $k$ is the number of commodities. Besides, when the network we consider is centralized, we prove that there is a $\frac{1}{\alpha}$-approximation algorithm for the sparsest cut problem, where $\alpha$ is the maximum weight ratio of vertices.

Key words: Multicommodity, Flow-cut gap, Sparsest cut, Approximation algorithm

CLC Number:

Rui Guan, Dong-Yue Liang, Wei Wang, Wei-Hua Yang. Direct Product Multicommodity Max-Concurrent-Flow Min-Sparse-Cut Theorem[J]. Journal of the Operations Research Society of China, 2026, 14(2): 719-729.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00567-8

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/719

References

[1] Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. In: The Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 553-562(2005)
[2] Aumann, Y., Rabani, Y.: An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27, 291–301(1998)
[3] Baïou, M., Barahona, F.: Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem. Math. Program. 172, 59–75(2018)
[4] Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300–343(1984)
[5] Chawla, S., Gupta, A., Räcke, H.: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms 4, 1–18(2008)
[6] Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15, 94–114(2006)
[7] Chekuri, C., Shepherd, F.B., Weibel, C.: Flow-cut gaps for integer and fractional multiflows. J. Comb. Theory Ser. B 103, 248–273(2013)
[8] Garg, N., Könemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37, 630–652(2007)
[9] Garg, N., Kumar, N., Sebö, A.: Integer plane multiflow maximisation: one-quarter-approximation and gaps. Math. Program. 175, 1–17(2021)
[10] Gupta, A., Talwar, K., Witmer, D.: Sparsest cut on bounded treewidth graphs: algorithms and hardness results. In: The Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, pp. 281-290(2013)
[11] Khot, S.A., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into L1. J. ACM 62, 1–39(2015)
[12] Klein, P., Rao, S., Agrawal, A., Ravi, R.: An approximate max-flow min-cut relation for undirected multicommodity flow, with applications. Combinatorica 15, 187–202(1995)
[13] Krauthgamer, R., Lee, J.R., Rika, H.: Flow-cut gaps and face covers in planar graphs. In: The Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 525-534(2019)
[14] Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46, 787–832(1999)
[15] Madan, R., Shah, D., Leveque, O.: Product multicommodity flow in wireless networks. IEEE Trans. Inf. Theory 54, 1460–1476(2008)
[16] Matula, D.W., Shahrokhi, F.: Sparsest cuts and bottlenecks in graphs. Discret. Appl.Math. 27, 113–123(1990)
[17] Plotkin, S.A., Tardos, É.: Improved bounds on the max-flow min-cut ratio for multicommodity flows. Combinatorica 15, 425–434(1995)
[18] Salmasi, A., Sidiropoulos, A., Sridhar, V.: On constant multi-commodity flow-cut gaps for families of directed minor-free graphs. In: The Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 535-553(2019)

Direct Product Multicommodity Max-Concurrent-Flow Min-Sparse-Cut Theorem

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Hao Xiao, Qian Liu, Yang Zhou, Min Li. Approximation Algorithms for k-Submodular Maximization Subject to a Knapsack Constraint [J]. Journal of the Operations Research Society of China, 2026, 14(2): 397-412.
[2]	Zhen Zhang, Zi-Yun Huang, Zhi-Ping Tian, Li-Mei Liu, Xue-Song Xu, Qi-Long Feng. On the Budgeted Priority p-Median Problem in High-Dimensional Euclidean Spaces [J]. Journal of the Operations Research Society of China, 2026, 14(1): 309-324.
[3]	Shu-Fang Gong, Bin Liu, Qi-Zhi Fang. Streaming Algorithms for Maximizing k-Submodular Functions with the Multi-knapsack Constraint [J]. Journal of the Operations Research Society of China, 2026, 14(1): 325-343.
[4]	Peng-Xiang Pan, Jun-Ran Lichen, Wen-Cheng Wang, Li-Jian Cai, Jian-Ping Li. Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints [J]. Journal of the Operations Research Society of China, 2025, 13(2): 535-554.
[5]	Pei-Jia Yang, Wen-Chang Luo. Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties [J]. Journal of the Operations Research Society of China, 2025, 13(1): 287-296.
[6]	Jian-Ping Li, Wen-Cheng Wang, Jun-Ran Lichen, Yu-Jie Zheng. Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R² Using Stock Pieces of Materials with Fixed Length [J]. Journal of the Operations Research Society of China, 2024, 12(4): 996-1021.
[7]	Jian-Ping Li, Su-Ding Liu, Jun-Ran Lichen, Peng-Xiang Pan, Wen-Cheng Wang. Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem [J]. Journal of the Operations Research Society of China, 2024, 12(3): 729-755.
[8]	Wen-Zhao Liu, Min Li. An Approximation Algorithm Based on Seeding Algorithm for Fuzzy k-Means Problem with Penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 387-409.
[9]	Fan Yuan, Da-Chuan Xu, Dong-Lei Du, Dong-Mei Zhang. Local search yields a PTAS for fixed-dimensional k-means problem with penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 351-362.
[10]	Bin Liu, Hui Su, Shu-Fang Gong, Qi-Zhi Fang. Adaptive Algorithms on Maximizing Monotone Nonsubmodular Functions [J]. Journal of the Operations Research Society of China, 2024, 12(2): 428-445.
[11]	Hong-Ye Zheng, Suo-Gang Gao, Wen Liu, Bo Hou. An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 495-504.
[12]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Correlation Clustering [J]. Journal of the Operations Research Society of China, 2023, 11(4): 911-924.
[13]	Amina Sabir, Peng-Fei Huang, Qing-Zhi Yang. The Low-Rank Approximation of Fourth-Order Partial-Symmetric and Conjugate Partial-Symmetric Tensor [J]. Journal of the Operations Research Society of China, 2023, 11(4): 735-758.
[14]	Jin-Shuang Guo, Wen Liu, Bo Hou. An Approximation Algorithm for P-prize-collecting Set Cover Problem [J]. Journal of the Operations Research Society of China, 2023, 11(1): 207-218.
[15]	Wei Yu, Rui-Yong Dai, Zhao-Hui Liu. Approximation Algorithms for Multi-vehicle Stacker Crane Problems [J]. Journal of the Operations Research Society of China, 2023, 11(1): 109-132.