License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.87
URN: urn:nbn:de:0030-drops-187406
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18740/
Panagiotas, Ioannis ;
Pichon, Grégoire ;
Singh, Somesh ;
Uçar, Bora
Engineering Fast Algorithms for the Bottleneck Matching Problem
Abstract
We investigate the maximum bottleneck matching problem in bipartite graphs. Given a bipartite graph with nonnegative edge weights, the problem is to find 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.
BibTeX - Entry
@InProceedings{panagiotas_et_al:LIPIcs.ESA.2023.87,
author = {Panagiotas, Ioannis and Pichon, Gr\'{e}goire and Singh, Somesh and U\c{c}ar, Bora},
title = {{Engineering Fast Algorithms for the Bottleneck Matching Problem}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {87:1--87:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18740},
URN = {urn:nbn:de:0030-drops-187406},
doi = {10.4230/LIPIcs.ESA.2023.87},
annote = {Keywords: bipartite graphs, assignment problem, matching}
}
