We provide a $5/4$-approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. This improves upon the previous best ratio of $4/3$. The algorithm is based on applying local improvement steps on a starting solution provided by a standard ear decomposition together with the idea of running several iterations on residual graphs by excluding certain edges that do not belong to an optimum solution. The latter idea is a novel one, which allows us to bypass $3$-ears with no loss in approximation ratio, the bottleneck for obtaining a performance guarantee below $3/2$. Our algorithm also implies a simpler $7/4$-approximation algorithm for the matching augmentation problem, which was recently treated.


翻译:我们为最小的两端连接的覆盖子图问题提供了5/4美元的接近算法。这比以前的最佳比率4/3美元有所改进。算法的基础是对标准耳分解提供的起始解决方案采用当地改良步骤,同时在残余图上运行若干迭代,排除某些不属于最佳解决办法的边缘。后一种想法是一个新颖的想法,使我们能够绕过3美元ears,而近似率没有亏损,这是获得3/2美元以下性能保证的瓶颈。我们的算法还意味着为匹配的扩增问题采用更简单的7/4美元的近似算法,这个问题最近得到了处理。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
【Manning新书】现代Java实战,592页pdf
专知会员服务
99+阅读 · 2020年5月22日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
(TensorFlow)实时语义分割比较研究
机器学习研究会
9+阅读 · 2018年3月12日
carla无人驾驶模拟中文项目 carla_simulator_Chinese
CreateAMind
3+阅读 · 2018年1月30日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年6月29日
Arxiv
0+阅读 · 2021年6月27日
Arxiv
0+阅读 · 2021年6月24日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
(TensorFlow)实时语义分割比较研究
机器学习研究会
9+阅读 · 2018年3月12日
carla无人驾驶模拟中文项目 carla_simulator_Chinese
CreateAMind
3+阅读 · 2018年1月30日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员