Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2303.12325 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918376560918528 |
|---|---|
| author | Nasre, Meghana Nimbhorkar, Prajakta Ranjan, Keshav |
| author_facet | Nasre, Meghana Nimbhorkar, Prajakta Ranjan, Keshav |
| contents | We study the many-to-many bipartite matching problem in the presence of preferences where ties, as well as lower quotas, may appear on both sides of the bipartition. The input is a bipartite graph $G=(A \cup B, E)$, where each vertex in $A \cup B$ has a positive upper quota and a non-negative lower quota denoting the maximum and minimum number of vertices that can be assigned to it from its neighborhood. Additionally, each vertex specifies a preference ordering, possibly containing ties, over its neighbors. A \textit{critical} matching is a matching which fulfills vertex lower quotas to the maximum possible extent. We seek to compute a matching that is critical as well as optimal with respect to the preferences of vertices. Stability, a well-accepted notion of optimality in the presence of two-sided preferences, is generalized to weak-stability in the presence of ties. However, a matching that is critical as well as weakly stable may not exist. Popularity is another well-investigated notion of optimality for the two-sided preference model; however, in the presence of ties (even without lower quotas), a popular matching may not exist. We, therefore, consider the notion of relaxed stability, which was introduced and studied by Krishnaa, Limaye, Nasre, and Nimbhorkar~(JoCO 2023). We show that a matching that is critical as well as relaxed-stable always exists, although computing a maximum-size relaxed-stable matching turns out to be NP-hard. Our main contribution achieves a $\frac{2}{3}$-approximation to the maximum cardinality critical relaxed-stable matching in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_12325 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting Nasre, Meghana Nimbhorkar, Prajakta Ranjan, Keshav Data Structures and Algorithms 05C85, 68W25 We study the many-to-many bipartite matching problem in the presence of preferences where ties, as well as lower quotas, may appear on both sides of the bipartition. The input is a bipartite graph $G=(A \cup B, E)$, where each vertex in $A \cup B$ has a positive upper quota and a non-negative lower quota denoting the maximum and minimum number of vertices that can be assigned to it from its neighborhood. Additionally, each vertex specifies a preference ordering, possibly containing ties, over its neighbors. A \textit{critical} matching is a matching which fulfills vertex lower quotas to the maximum possible extent. We seek to compute a matching that is critical as well as optimal with respect to the preferences of vertices. Stability, a well-accepted notion of optimality in the presence of two-sided preferences, is generalized to weak-stability in the presence of ties. However, a matching that is critical as well as weakly stable may not exist. Popularity is another well-investigated notion of optimality for the two-sided preference model; however, in the presence of ties (even without lower quotas), a popular matching may not exist. We, therefore, consider the notion of relaxed stability, which was introduced and studied by Krishnaa, Limaye, Nasre, and Nimbhorkar~(JoCO 2023). We show that a matching that is critical as well as relaxed-stable always exists, although computing a maximum-size relaxed-stable matching turns out to be NP-hard. Our main contribution achieves a $\frac{2}{3}$-approximation to the maximum cardinality critical relaxed-stable matching in polynomial time. |
| title | Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting |
| topic | Data Structures and Algorithms 05C85, 68W25 |
| url | https://arxiv.org/abs/2303.12325 |