On Three Approaches to Length-Bounded Maximum Multicommodity Flow with Unit Edge-Lengths

  • Pavel Borisovsky Sobolev Institute of Mathematics SB RAS, 13 Pevtsov str., 644099, Omsk, Russia
  • Sergei Hrushev Sobolev Institute of Mathematics SB RAS, 13 Pevtsov str., 644099, Omsk, Russia
  • Vadim Teplyakov Yaliny Research and Development Center, 2 Paveletskaya naberezhnaya, block 2, 115114, Moscow, Russia
  • Mikhail Vorozhtsov Yaliny Research and Development Center, 2 Paveletskaya naberezhnaya, block 2, 115114, Moscow, Russia
  • Anton V. Eremeev Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Novosibirsk State University

Abstract

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.

Published
Dec 12, 2018
How to Cite
BORISOVSKY, Pavel et al. On Three Approaches to Length-Bounded Maximum Multicommodity Flow with Unit Edge-Lengths. Yugoslav Journal of Operations Research, [S.l.], v. 29, n. 1, p. 93–112, dec. 2018. ISSN 2334-6043. Available at: <http://www.yujor.fon.bg.ac.rs/index.php/yujor/article/view/684>. Date accessed: 28 mar. 2024.
Section
Articles