2019/04/20 by Liu, Pengfei
#90B10 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1904.09397
This paper researches combinatorial algorithms for the multi-commodity flow problem. We relax the capacity constraints and introduce a penalty function h for each arc. If the flow exceeds the capacity on arc a, arc a would have a penalty cost. Based on the penalty function h, a new conception, equilibrium pseudo-flow, is introduced. Then we design a combinatorial algorithm to obtain equilibrium pseudo-flow. If the equilibrium pseudo-flow is a nonzero-equilibrium pseudo-flow, there exists no feasible solution for the multi-commodity flow problem; if the equilibrium pseudo-flow is a zero-equilibrium pseudo-flow, there exists a feasible solution for the multi-commodity flow problem and the zero-equilibrium pseudo-flow is the feasible solution. At last, a non-linear description of the multi-commodity flow problem is given, whose solution is equilibrium pseudo-flow. Besides, the content in this paper can be easily generalized to minimum cost multi-commodity flow problem.