11 DEZEMBRO / SEGUNDA FEIRA / 13:09
FCUP PT 
 EN
 
 
APRESENTAÇÃO
PESSOAS
ENSINO
INVESTIGAÇÃO
BIBLIOTECA
NOTÍCIAS
CONTACTOS

Technical Report: DCC-2013-05

Maximizing expectation on vertex-disjoint cycle packing

João Pedro Pedroso

DCC-FC & INESC Porto, Universidade do Porto
e-mail: jpp@dcc.fc.up.pt
March 2013

Abstract

This paper proposes a method for computing the expectation for the length of the maximum set of vertex-disjoint cycles in a digraph where vertices and/or arcs are subject to failure with a known probability. This method has an immediate practical application: it can be used for the solution of a kidney exchange program in the common situation where the underlying graph is unreliable. Results for realistic benchmark instances are reported and analyzed.
Keywords: Kidney exchange programs, Cycle packing, Expectation optimization, Combinatorial optimization.


FCUP 2017