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(\frac{\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.
翻译:鉴于交通的动态性质,我们调查了强大的网络设计变体,我们必须确定每个链接的储备能力,以便每个属于多面形集的需求矢量都能够选择路径。 目标是最大限度地减少拥堵或线性成本。 假设路流是分数和动态的( 取决于当前的交通矢量)。 我们首先证明, 任何恒定系数中都无法大致地证明具有最小拥堵的稳健网络设计问题。 然后, 使用 ET 的预测, 我们得到一个 $mega (\ frac) (\ frac) (frac) nunlog n_log n} ), 每条属于多线性路径的矢量矢量矢量矢量矢量目标。 这意味着2008年R\\\ a}cke 建立的众所周知的美元近似比率是分数和动态的。 使用 Lagrange Reformation, 我们的递减量和接近性结果的一个重要后果是, 即使线性预订成本较低, 也无法在任何恒定的网络中 。