OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Randomized rounding algorithms for large scale unsplittable flow problems

Lamothe, François and Rachelson, Emmanuel and Haït, Alain and Baudoin, Cedric and Dupé, Jean-Baptiste Randomized rounding algorithms for large scale unsplittable flow problems. (2021) Journal of Heuristics, 27 (6). 1081-1110. ISSN 1381-1231

[img]
Preview
(Document in English)

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
1MB

Official URL: https://doi.org/10.1007/s10732-021-09478-w

Abstract

Unsplittable flow problems cover a wide range of telecommunication and transporta- tion problems and their efficient resolution is key to a number of applications. In this work, we study algorithms that can scale up to large graphs and important num- bers of commodities. We present and analyze in detail a heuristic based on the linear relaxation of the problem and randomized rounding. We provide empirical evidence that this approach is competitive with state-of-the-art resolution methods either by its scaling performance or by the quality of its solutions. We provide a variation of the heuristic which has the same approximation factor as the state-of-the-art approxima- tion algorithm. We also derive a tighter analysis for the approximation factor of both the variation and the state-of-the-art algorithm. We introduce a new objective function for the unsplittable flow problem and discuss its differences with the classical con- gestion objective function. Finally, we discuss the gap in practical performance and theoretical guarantees between all the aforementioned algorithms.

Item Type:Article
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National d'Études Spatiales - CNES (FRANCE)
Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
Other partners > Thales (FRANCE)
Laboratory name:
Statistics:download
Deposited On:07 Feb 2022 10:07

Repository Staff Only: item control page