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

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)

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  -