Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2407.09798 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910526699732992 |
|---|---|
| author | Csáji, Gergely Király, Tamás Takazawa, Kenjiro Yokoi, Yu |
| author_facet | Csáji, Gergely Király, Tamás Takazawa, Kenjiro Yokoi, Yu |
| contents | We investigate weighted settings of popular matching problems with matroid constraints. The concept of popularity was originally defined for matchings in bipartite graphs, where vertices have preferences over the incident edges. There are two standard models depending on whether vertices on one or both sides have preferences. A matching $M$ is popular if it does not lose a head-to-head election against any other matching. In our generalized models, one or both sides have matroid constraints, and a weight function is defined on the ground set. Our objective is to find a popular optimal matching, i.e., a maximum-weight matching that is popular among all maximum-weight matchings satisfying the matroid constraints. For both one- and two-sided preferences models, we provide efficient algorithms to find such solutions, combining algorithms for unweighted models with fundamental techniques from combinatorial optimization. The algorithm for the one-sided preferences model is further extended to a model where the weight function is generalized to an M$^\natural$-concave utility function. Finally, we complement these tractability results by providing hardness results for the problems of finding a popular near-optimal matching. These hardness results hold even without matroid constraints and with very restricted weight functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09798 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Popular Maximum-Utility Matchings with Matroid Constraints Csáji, Gergely Király, Tamás Takazawa, Kenjiro Yokoi, Yu Computer Science and Game Theory We investigate weighted settings of popular matching problems with matroid constraints. The concept of popularity was originally defined for matchings in bipartite graphs, where vertices have preferences over the incident edges. There are two standard models depending on whether vertices on one or both sides have preferences. A matching $M$ is popular if it does not lose a head-to-head election against any other matching. In our generalized models, one or both sides have matroid constraints, and a weight function is defined on the ground set. Our objective is to find a popular optimal matching, i.e., a maximum-weight matching that is popular among all maximum-weight matchings satisfying the matroid constraints. For both one- and two-sided preferences models, we provide efficient algorithms to find such solutions, combining algorithms for unweighted models with fundamental techniques from combinatorial optimization. The algorithm for the one-sided preferences model is further extended to a model where the weight function is generalized to an M$^\natural$-concave utility function. Finally, we complement these tractability results by providing hardness results for the problems of finding a popular near-optimal matching. These hardness results hold even without matroid constraints and with very restricted weight functions. |
| title | Popular Maximum-Utility Matchings with Matroid Constraints |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2407.09798 |