Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running times, eventually leading to a $\tilde{O}(n^2)$-time algorithm (Karger, STOC 2020). This represented a natural culmination of this line of work because the algorithmic techniques used can enumerate $\Theta(n^2)$ (near)-minimum cuts. In this paper, we go beyond this quadratic barrier and obtain a faster algorithm for the network unreliability problem. Our algorithm runs in $m^{1+o(1)} + \tilde{O}(n^{1.5})$ time. Our main contribution is a new estimator for network unreliability in very reliable graphs. These graphs are usually the bottleneck for network unreliability since the disconnection event is elusive. Our estimator is obtained by defining an appropriate importance sampling subroutine on a dual spanning tree packing of the graph. To complement this estimator for very reliable graphs, we use recursive contraction for moderately reliable graphs. We show that an interleaving of sparsification and contraction can be used to obtain a better parametrization of the recursive contraction algorithm that yields a faster running time matching the one obtained for the very reliable case.


翻译:---- Karger(STOC 1995)提出了网络(不)可靠性问题的第一个FPTAS,随后的三十年内进行了研究,得到了越来越快的运行时间,最终导致了一个 $\tilde{O}(n^2)$ 时间算法(Karger,STOC 2020)。这代表了这一工作线的自然顶点,因为所使用的算法技术可以列举$\Theta(n^2)$(近似)最小割。在本文中,我们超越了这一二次时间障碍,获得了更快的网络不可靠性算法。我们的算法在$m^{1+o(1)}+\tilde{O}(n^{1.5})$ 时间内运行。我们的主要贡献是一个适用于非常可靠图形的新估计器。由于断开事件很难捕获,这些图形通常是网络不可靠性的瓶颈。我们通过在图形的双重生成树包中定义适当的重要性采样子程序来获得我们的估计器。为了补充非常可靠图形的估计器,我们使用递归收缩来处理中等可靠性图形。我们展示了稀疏化和收缩的交错可以用于获得更好的递归收缩算法的参数化,从而产生与非常可靠情况下所获得的相同的更快速度的运行时间。

0
下载
关闭预览

相关内容

【硬核书】树与网络上的概率,716页pdf
专知会员服务
71+阅读 · 2021年12月8日
专知会员服务
14+阅读 · 2021年5月21日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
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日
【泡泡一分钟】基于图神经网络的情景识别
泡泡机器人SLAM
11+阅读 · 2018年11月21日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】深度学习目标检测全面综述
机器学习研究会
21+阅读 · 2017年9月13日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
10+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
VIP会员
相关VIP内容
【硬核书】树与网络上的概率,716页pdf
专知会员服务
71+阅读 · 2021年12月8日
专知会员服务
14+阅读 · 2021年5月21日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
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日
【泡泡一分钟】基于图神经网络的情景识别
泡泡机器人SLAM
11+阅读 · 2018年11月21日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】深度学习目标检测全面综述
机器学习研究会
21+阅读 · 2017年9月13日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
10+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员