Paper Info
Title
On The Approximability Of Robust Network Design
Abstract
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 Omega(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 Racke 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 Omega(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. (C) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.tcs.2021.01.026
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Approximability, PCP, ETH, Robust network design
Journal
860
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Yacine Al-Najjar100.34
Ben Ameur Walid220528.43
Jeremie Leguay330328.78
Jocelyne Elias400.68