Maximum-expectation matching under recourse

João Pedro Pedroso, Shiro Ikeda

This paper addresses the problem of maximizing the expected size of a matching in the case of unreliable vertices and/or edges. The assumption is that upon failure, remaining verti…