Maximum-expectation matching under recourse

• Tipo: Artigo em Revista Científica Internacional
• Data: 2025

Autores

Joao Pedro Pedroso (Autor) FCUP; Ikeda, S (Autor) Outra

Revista

Título: European Journal of Operational Research

Vol. 324

Páginas: 732-741

ISSN: 0377-2217

Editora: Elsevier

Indexação

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-018-Q9M

DOI: 10.1016/j.ejor.2025.02.012

Abstract (EN): 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 the solution is built in several steps. In a given step, edges with successfully matched vertices are made permanent; but upon edge or vertex failures, the remaining vertices become eligible for reassignment. This process may be repeated a given number of times, and the objective is to end with the overall maximum number of matched vertices. An application of this problem is found in kidney exchange programs, going on in several countries, where a vertex is an incompatible patient¿donor pair and an edge indicates cross-compatibility between two pairs; the objective is to match these pairs so as to maximize the number of served patients. A new scheme is proposed for matching rearrangement in case of failure, along with a prototype algorithm for computing the optimal expectation for the number of matched edges (or vertices), considering a possibly limited number of rearrangements. Computational experiments reveal the relevance and limitations of the algorithm, in general terms and for the kidney exchange application. © 2025 The Authors

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 9