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, 我们的递减量和接近性结果的一个重要后果是, 即使线性预订成本较低, 也无法在任何恒定的网络中 。

0
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【ICLR-2020】网络反卷积,NETWORK DECONVOLUTION
专知会员服务
38+阅读 · 2020年2月21日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
“CVPR 2020 接受论文列表 1470篇论文都在这了
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Faster R-CNN
数据挖掘入门与实战
4+阅读 · 2018年4月20日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Arxiv
0+阅读 · 2021年3月24日
VIP会员
相关VIP内容
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【ICLR-2020】网络反卷积,NETWORK DECONVOLUTION
专知会员服务
38+阅读 · 2020年2月21日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
“CVPR 2020 接受论文列表 1470篇论文都在这了
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Faster R-CNN
数据挖掘入门与实战
4+阅读 · 2018年4月20日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Top
微信扫码咨询专知VIP会员