Effective heuristics for matchings in hypergraphs

The problem of finding a maximum cardinality matching in a d-partite d-uniform hypergraph is an important problem in combinatorial optimization and has beentheoretically analyzed by several researchers. In this work, we first devise heuristics for this problem by generalizing the existing cheap graph matching heuristics. Then, we propose a novel heuristic based on tensor scaling to extend the matching via judicious hyperedge selections. Experiments on random, synthetic and real-life hypergraphs show that this new heuristic is highly practical and superior to the others on finding a matching with largecardinality.; Le problème consistant à trouver un couplage maximal dans un hypergraphe uniforme ayant d parts est un problème important en optimisation combinatoire. Dans ce travail, nous concevons d’abord des heuristiques pour ce problème en généralisant les heuristiques de couplage dans des graphes. Ensuite, nous proposons une nouvelle heuristique basée sur des méthodes de mise à l’échelle de tenseur pour étendre le couplage via des sélections judicieuses d’hyperarêtes. Des expériences sur des hypergraphes aléatoires, synthétiques et réels montrent que cette nouvelle heuristique est simple à mettre en pratique et supérieure aux autres pour trouver des couplages de grande cardinalité.