Engineering fast algorithms for the bottleneck matching problem

Autor: Panagiotas, Ioannis, Pichon, Grégoire, Singh, Somesh, Uçar, Bora
Přispěvatelé: Neo4j, Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)
Jazyk: angličtina
Rok vydání: 2023
Předmět:
Zdroj: ESA 2023-The 31st Annual European Symposium on Algorithms
ESA 2023-The 31st Annual European Symposium on Algorithms, Sep 2023, Amsterdam (Hollande), Netherlands
Popis: International audience; We investigate the maximum bottleneck matching problem in bipartite graphs. Given a bipartite graph with nonnegative edge weights, the problem is to determine a maximum cardinality matching in which the minimum weight of an edge is the maximum. To the best of our knowledge, there are two widely used solvers for this problem based on two different approaches. There exists a third known approach in the literature, which seems inferior to those two which is presumably why there is no implementation of it. We take this third approach, make theoretical observations to improve its behavior, and implement the improved method. Experiments with the existing two solvers show that their run time can be too high to be useful in many interesting cases. Furthermore, their performance is not predictable, and slight perturbations of the input graph lead to considerable changes in the run time. On the other hand, the proposed solver's performance is much more stable; it is almost always faster than or comparable to the two existing solvers, and its run time always remains low.
Databáze: OpenAIRE