Proceedings of the International Conference on Logistics, Engineering, Management and Computer Science

Approximation Algorithm for Extended Maximum---- Concurrent Flow Problem with Saturated Capacity

Authors
Congdian Cheng, Jingxin Ma
Corresponding Author
Congdian Cheng
Available Online July 2015.
DOI
10.2991/lemcs-15.2015.96How to use a DOI?
Keywords
Network; Multicommodity flow; Concurrent flow; Approximation algorithm; Approximation measure
Abstract

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.

Copyright
© 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/).

Download article (PDF)

Volume Title
Proceedings of the International Conference on Logistics, Engineering, Management and Computer Science
Series
Advances in Intelligent Systems Research
Publication Date
July 2015
ISBN
10.2991/lemcs-15.2015.96
ISSN
1951-6851
DOI
10.2991/lemcs-15.2015.96How to use a DOI?
Copyright
© 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  -