On the approximability of robust network design - Télécom SudParis Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2021

On the approximability of robust network design

Résumé

Given the dynamic nature of traffic, we investigate the variant of robust network design where we have to determine the capacity to reserve on each link so that each demand vector belonging to a polyhedral set can be routed. The objective is either to minimize congestion or a linear cost. Routing is assumed to be fractional and dynamic (i.e., dependent on the current traffic vector). We first prove that the robust network design problem with minimum congestion cannot be approximated within any constant factor. Then, using the ETH conjecture, we get a Ω(log⁡n/log⁡log⁡n) lower bound for the approximability of this problem. This implies that the well-known O(log⁡n) approximation ratio established by Räcke in 2008 is tight. Using Lagrange relaxation, we obtain a new proof of the O(log⁡n) approximation. An important consequence of the Lagrange-based reduction and our inapproximability results is that the robust network design problem with linear reservation cost cannot be approximated within any constant ratio. This answers a long-standing open question of Chekuri (2007). We also give another proof of the result of Goyal et al. (2009) stating that the optimal linear cost under static routing can be Ω(log⁡n) more expensive than the cost obtained under dynamic routing. Finally, we show that even if only two given paths are allowed for each commodity, the robust network design problem with minimum congestion or linear cost is hard to approximate within some constant.
Fichier principal
Vignette du fichier
S0304397521000463.pdf (733.27 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03557332 , version 1 (09-03-2023)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

Citer

Yacine Al-Najjar, Walid Ben-Ameur, Jérémie Leguay. On the approximability of robust network design. Theoretical Computer Science, 2021, 860, pp.41-50. ⟨10.1016/j.tcs.2021.01.026⟩. ⟨hal-03557332⟩
28 Consultations
13 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More