A combinatorial approximation algorithm for concurrent flow problem and its application

摘要

The multi-commodity flow problem involves simultaneous shipping several different commodities from sources to sinks in a directed network with total amount of flow going through an edge limited by its capacity. The optimization version of the multi-commodity flow problem is the maximum concurrent flow problem, which finds a flow with the minimum congestion. For any positive ε, the ε-optimal concurrent flow problem is to find a solution whose the congestion value is no more than (1+ε) times the minimum congestion. In recent years, a few fast combinatorial approximation algorithms for the ε-optimal concurrent flow problem have been presented. In this paper we propose a new variant of the combinatorial approximation algorithm: CACF with a tighter computation bound in decreasing the values of congestion and the potential function. Numerical comparisons are made between the results obtained by the combinatorial approximation algorithms and those did by the linear programming package CPLEX on large-scale test networks. The application of CACF to efficiently solving the system-optimal network flow problem is given where good results have been obtained. It has shown the capacity of the CACF in dealing with problems of concurrent flow associated.