A polynomial-time approximation algorithm for all-terminal network reliability

浙江大学数学科学学院九十周年院庆系列活动之三

题目：A polynomial-time approximation algorithm for all-terminal network reliability
地点：浙江大学玉泉校区工商楼200-9
时间：2018年6月7日（星期四） 下午16点开始
报告人：Heng Guo,  School of Informatics, University of Edinburgh


摘要：All-terminal network reliability is the probability that, in a undirected graph,
 assuming each edge fails independently, the remaining graph is still connected.
We will present a fully polynomial-time randomised approximation scheme (FPRAS) for
this problem. Our main contribution is to confirm a conjecture by Gorodezky and Pak
(Random Struct. Algorithms, 2014), that the expected running time of the “cluster-popping”
algorithm in bi-directed graphs is bounded by a polynomial in the size of the input.


主讲人简介: Heng Guo is a lecturer in algorithm and complexity, in the School of Informatics,
University of Edinburgh. He joined Edinburgh after working for two years in Berkeley and London.
 Before that, he completed his Ph.D. in the University of Wisconsin - Madison in 2015, which
has won the EATCS Distinguished Dissertation award.


联系人： 王伟（wangw07@zju.edu.cn）