Effective heuristics for matchings in hypergraphs

Warning The system is temporarily closed to updates for reporting purpose.

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)

Abstract

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