Considering the dynamic nature of traffic, the robust network design problem consists in computing the capacity to be reserved on each network link such that any demand vector belonging to a polyhedral set can be routed. The objective is either to minimize congestion or a linear cost. And routing freely depends on the demand . 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 R\"{a}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 . 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 costs is hard to approximate within some constant k .
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 R\"{a}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\&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 .
R
Considering
Given
R
the
we investigate the variant of
R
problem consists in computing
where we have to determine
R
be reserved on each network link such that any
reserve on each link so that each
R
And routing freely depends on the demand
Routing is assumed to be fractional and dynamic (i.e., dependent on the current traffic vector)
R
.
(2007). We also give another proof of the result of Goyal\&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.
R
costs
cost
D
k