Perfect Matchings and Popularity in the Many-to-Many Setting
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913569610661888 |
|---|---|
| author | Kavitha, Telikepalli Makino, Kazuhisa |
| author_facet | Kavitha, Telikepalli Makino, Kazuhisa |
| contents | We consider a matching problem in a bipartite graph $G$ where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on the edge set. We assume $G$ admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible for us and we are interested in those perfect matchings that are popular within the set of perfect matchings. It is known that such matchings (called popular perfect matchings) always exist and can be efficiently computed. What we seek here is not any popular perfect matching, but a min-cost one. We show a polynomial-time algorithm for finding such a matching; this is via a characterization of popular perfect matchings in $G$ in terms of stable matchings in a colorful auxiliary instance. This is a generalization of such a characterization that was known in the one-to-one setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_00384 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Perfect Matchings and Popularity in the Many-to-Many Setting Kavitha, Telikepalli Makino, Kazuhisa Data Structures and Algorithms We consider a matching problem in a bipartite graph $G$ where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on the edge set. We assume $G$ admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible for us and we are interested in those perfect matchings that are popular within the set of perfect matchings. It is known that such matchings (called popular perfect matchings) always exist and can be efficiently computed. What we seek here is not any popular perfect matching, but a min-cost one. We show a polynomial-time algorithm for finding such a matching; this is via a characterization of popular perfect matchings in $G$ in terms of stable matchings in a colorful auxiliary instance. This is a generalization of such a characterization that was known in the one-to-one setting. |
| title | Perfect Matchings and Popularity in the Many-to-Many Setting |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.00384 |