We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by one unit in the cheapest possible way. More precisely, given a $k$-edge-connected graph $G=(V,E)$ and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to $G$ makes the graph $(k+1)$-edge-connected. If $k$ is odd, the problem is known to reduce to the Tree Augmentation Problem (TAP) -- i.e., $G$ is a spanning tree -- for which significant progress has been achieved recently, leading to approximation factors below $1.5$ (the currently best factor is $1.458$). However, advances on TAP did not carry over to CAP so far. Indeed, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain the first approximation factor below $2$ for CAP by presenting a $1.91$-approximation algorithm based on a method that is disjoint from recent advances for TAP. We first bridge the gap between TAP and CAP, by presenting techniques that allow for leveraging insights and methods from TAP to approach CAP. We then introduce a new way to get approximation factors below $1.5$, based on a new analysis technique. Through these ingredients, we obtain a $1.393$-approximation algorithm for CAP, and therefore also TAP. This leads to the currently best approximation result for both problems in a unified way, by significantly improving on the above-mentioned $1.91$-approximation for CAP and also the previously best approximation factor of $1.458$ for TAP by Grandoni, Kalaitzis, and Zenklusen (STOC 2018). Additionally, a feature we inherit from recent TAP advances is that our approach can deal with the weighted setting when the ratio between the largest to smallest cost on extra links is bounded, in which case we obtain approximation factors below $1.5$.


翻译:我们认为连接增强问题(CAP)是统一网络设计领域一个典型的问题。这是一个在可生存的网络设计领域的典型问题。它涉及以最廉价的方式增加一个单位的图表的边际连接性。更准确地说,考虑到一个以美元为顶尖的相联图形$G=(V,E)和一组额外的边端,我们的任务是找到一个最起码的基点子子,其中加到G$的外端点使图(k+1美元)相联。如果美元是奇数,问题就在于如何降低树强化问题(TAP)的边际连接性。也就是说,G$是一棵横贯的树,最近已经取得了显著的进展,导致1.5美元(目前的最佳因素是1.458美元 ) 。然而,TAP的进展并没有一直持续到CAP的顶端端点。 事实上,直到最近,Byrka, Grandoni, 和Amelili (STOC 2020) 才能获得第一个低于2美元的基点的基点, 也就是我们第一次提出191美元为顶端的基点,因此, 美元为GG$为底的基价的基点算算。

0
下载
关闭预览

相关内容

ACM应用感知TAP(ACM Transactions on Applied Perception)旨在通过发表有助于统一这些领域研究的高质量论文来增强计算机科学与心理学/感知之间的协同作用。该期刊发表跨学科研究,在跨计算机科学和感知心理学的任何主题领域都具有重大而持久的价值。所有论文都必须包含感知和计算机科学两个部分。主题包括但不限于:视觉感知:计算机图形学,科学/数据/信息可视化,数字成像,计算机视觉,立体和3D显示技术。听觉感知:听觉显示和界面,听觉听觉编码,空间声音,语音合成和识别。触觉:触觉渲染,触觉输入和感知。感觉运动知觉:手势输入,身体运动输入。感官感知:感官整合,多模式渲染和交互。 官网地址:http://dblp.uni-trier.de/db/journals/tap/
最新《自监督表示学习》报告,70页ppt
专知会员服务
85+阅读 · 2020年12月22日
专知会员服务
42+阅读 · 2020年12月18日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
39+阅读 · 2020年9月6日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
计算机类 | LICS 2019等国际会议信息7条
Call4Papers
3+阅读 · 2018年12月17日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
NIPS 2017:贝叶斯深度学习与深度贝叶斯学习(讲义+视频)
机器学习研究会
36+阅读 · 2017年12月10日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年1月14日
Augmentation for small object detection
Arxiv
11+阅读 · 2019年2月19日
VIP会员
相关VIP内容
最新《自监督表示学习》报告,70页ppt
专知会员服务
85+阅读 · 2020年12月22日
专知会员服务
42+阅读 · 2020年12月18日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
39+阅读 · 2020年9月6日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
计算机类 | LICS 2019等国际会议信息7条
Call4Papers
3+阅读 · 2018年12月17日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
NIPS 2017:贝叶斯深度学习与深度贝叶斯学习(讲义+视频)
机器学习研究会
36+阅读 · 2017年12月10日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员