Effective heuristics for matchings in hypergraphs

Dufossé, Fanny and Kaya, Kamer and Panagiotas, Ioannis and Uçar, Bora (2019) Effective heuristics for matchings in hypergraphs. In: Special Event on Analysis of Experimental Algorithms, SEA² 2019, Kalamata, Greece

Full text not available from this repository. (Request a copy)


The problem of finding a maximum cardinality matching in a d-partite, d-uniform hypergraph is an important problem in combinatorial optimization and has been theoretically analyzed. We first generalize some graph matching heuristics for this problem. We then 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 large cardinality.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: d-dimensional matching; Karp-Sipser heuristic; Matching in hypergraphs; Tensor scaling
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 28 Jul 2023 22:24
Last Modified: 28 Jul 2023 22:24
URI: https://research.sabanciuniv.edu/id/eprint/46394

Actions (login required)

View Item
View Item