A new approach to bipartite stable matching optimization
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_ | 1866918199609524224 |
|---|---|
| author | Fleiner, Tamás Frank, András Király, Tamás |
| author_facet | Fleiner, Tamás Frank, András Király, Tamás |
| contents | As a common generalization of previously solved optimization problems concerning bipartite stable matchings, we describe a strongly polynomial network flow based algorithm for computing $\ell$ disjoint stable matchings with minimum total cost. The major observation behind the approach is that stable matchings, as edge sets, can be represented as certain cuts of an associated directed graph. This allows us to use results on disjoint cuts directly to answer questions about disjoint stable matchings. We also provide a construction that represents stable matchings as maximum-size antichains in a partially ordered set (poset), which enables us to apply the theorems of Dilworth, Mirsky, Greene and Kleitman directly to stable matchings. Another consequence of these approaches is a min-max formula for the minimum number of stable matchings covering all stable edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04885 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A new approach to bipartite stable matching optimization Fleiner, Tamás Frank, András Király, Tamás Computer Science and Game Theory Data Structures and Algorithms Combinatorics As a common generalization of previously solved optimization problems concerning bipartite stable matchings, we describe a strongly polynomial network flow based algorithm for computing $\ell$ disjoint stable matchings with minimum total cost. The major observation behind the approach is that stable matchings, as edge sets, can be represented as certain cuts of an associated directed graph. This allows us to use results on disjoint cuts directly to answer questions about disjoint stable matchings. We also provide a construction that represents stable matchings as maximum-size antichains in a partially ordered set (poset), which enables us to apply the theorems of Dilworth, Mirsky, Greene and Kleitman directly to stable matchings. Another consequence of these approaches is a min-max formula for the minimum number of stable matchings covering all stable edges. |
| title | A new approach to bipartite stable matching optimization |
| topic | Computer Science and Game Theory Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2409.04885 |