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
2018-12-12
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: <https://yujor.fon.bg.ac.rs/index.php/yujor/article/view/684>. Date accessed: 24 nov. 2024.
Citation Formats
Issue
Vol 29 No 1 (2019)
Section
Articles
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.