Approximation Algorithm for Extended Maximum---- Concurrent Flow Problem with Saturated Capacity
- 10.2991/lemcs-15.2015.96How to use a DOI?
- Network; Multicommodity flow; Concurrent flow; Approximation algorithm; Approximation measure
The Maximum Concurrent Flow is a classical mu-lticommodity flow problem and has a extensive applications in the practice such as transportations, communications and network designs. It has important sense not only in theory, but also in practice to develop this kind of multicommodity flow problem. This work studied a kind of extensive maximum concurrent flow problem (EMCFPSC). The major contributions are as follows: (A) Propose the definition of the problem EMCFPSC and prove its solutions exist. (B) Design an approximation algorithm to solve EMCFPSC through constructing auxiliary network and implementing the binary search by a full polynomial time approximation scheme (FPTAS) , presented by Korte and Vygen in 2000 from the framework of Garg and Könemann , to find approximate solutions of Maximum Multicommodity Flow Problem. (C) Propose and analyse the complexity and the approximation measure of the designed algorithm. (D) Shown that the designed approximation algorithm is a FPTAS to solve the problem EMCFPSC.
- © 2015, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Congdian Cheng AU - Jingxin Ma PY - 2015/07 DA - 2015/07 TI - Approximation Algorithm for Extended Maximum---- Concurrent Flow Problem with Saturated Capacity BT - Proceedings of the International Conference on Logistics, Engineering, Management and Computer Science PB - Atlantis Press SP - 506 EP - 510 SN - 1951-6851 UR - https://doi.org/10.2991/lemcs-15.2015.96 DO - 10.2991/lemcs-15.2015.96 ID - Cheng2015/07 ER -