Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914521466011648 |
|---|---|
| author | Hathcock, Daniel Ravi, R. |
| author_facet | Hathcock, Daniel Ravi, R. |
| contents | Given a bipartite graph that has a perfect matching, a prefect proportional allocation is an assignment of positive weights to the nodes of the right partition so that every left node is fractionally assigned to its neighbors in proportion to their weights, and these assignments define a fractional perfect matching. We prove that a bipartite graph has a perfect proportional allocation if and only if it is matching covered, by using a classical result on matrix scaling. We also present an extension of this result to provide a simple allocation strategy in non-matching covered bipartite graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01107 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations Hathcock, Daniel Ravi, R. Data Structures and Algorithms Combinatorics Given a bipartite graph that has a perfect matching, a prefect proportional allocation is an assignment of positive weights to the nodes of the right partition so that every left node is fractionally assigned to its neighbors in proportion to their weights, and these assignments define a fractional perfect matching. We prove that a bipartite graph has a perfect proportional allocation if and only if it is matching covered, by using a classical result on matrix scaling. We also present an extension of this result to provide a simple allocation strategy in non-matching covered bipartite graphs. |
| title | Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2510.01107 |