On Three Approaches to Length-Bounded Maximum Multicommodity Flow with Unit Edge-Lengths - Borisovsky, Pavel; Hrushev, Sergei; Teplyakov, Vadim; Vorozhtsov, Mikhail; Eremeev, Anton V. (Yugoslav Journal of Operations Research, 2018)
The paper presents a comparison of three approaches to solving the length-bounded maximum multicommodity flow problem with unit edge-lengths. Following the approach of Garg and Konemann, we developed an improved fully polynomial-time approximation scheme for this problem. As the second alternative, we consider the well-known greedy approach. The third approach yields exact solutions by means of a standard LP solver applied to an LP model on the time-expanded network. Computational experiments are carried out on benchmark graphs and on graphs that model software-defined satellite networks to compare the proposed algorithms and an exact linear programming solver. The results of the experiments demonstrate a trade-off between the computing time and the precision of algorithms under consideration.