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)
Official URL: https://dx.doi.org/10.1007/978-3-030-34029-2_17
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