高级检索
Partial rejection sampling (PRS) is an algorithm which bridges approximate counting/sampling and Lovasz local lemma. We will explain how PRS works, show its correctness, and discuss a formula for its expected running time in some special but very useful cases. With this technique, we will give a fully polynomial-time randomised approximation algorithm for all-terminal network reliability. Time permitting, we will cover a few other related applications as well.
可靠性
郭珩