Bipartite matching under communication constraints
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911586790146048 |
|---|---|
| author | Mohanty, Moonmoon Bolar, Gautham Patil, Preetam Ganesh, Ayalvadi Chamberland, Jean-Francois Parag, Parimal |
| author_facet | Mohanty, Moonmoon Bolar, Gautham Patil, Preetam Ganesh, Ayalvadi Chamberland, Jean-Francois Parag, Parimal |
| contents | In modern data center networks, thousands of hosts contend for shared link capacity; the scale of these systems makes centralized scheduling impractical. This article models such scheduling as a bipartite matching problem under communication constraints: senders express interest in forming connections, and receivers respond using only locally available information. A class of single-round probabilistic matching algorithms is proposed, built on two key ideas: degree-biased sampling, in which senders use receiver degrees to inform their random selection, and random thinning, in which senders report only a random subset of their connections. Analytical performance guarantees are established for random graph models. In sparse regimes, degree-biased sampling yields a higher expected matching size than prior communication-constrained algorithms; in denser settings, a counterintuitive phenomenon emerges where deliberately restricting available connections through thinning increases the expected number of matches. Combining thinning to degree two with greedy selection produces an algorithm that requires no parameter tuning and, in packet-level simulations with production traffic traces, significantly extends the network stability region. Although motivated by data center network scheduling, the underlying framework of bipartite matching under local information constraints is portable to other resource allocation settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_10744 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Bipartite matching under communication constraints Mohanty, Moonmoon Bolar, Gautham Patil, Preetam Ganesh, Ayalvadi Chamberland, Jean-Francois Parag, Parimal Distributed, Parallel, and Cluster Computing Networking and Internet Architecture In modern data center networks, thousands of hosts contend for shared link capacity; the scale of these systems makes centralized scheduling impractical. This article models such scheduling as a bipartite matching problem under communication constraints: senders express interest in forming connections, and receivers respond using only locally available information. A class of single-round probabilistic matching algorithms is proposed, built on two key ideas: degree-biased sampling, in which senders use receiver degrees to inform their random selection, and random thinning, in which senders report only a random subset of their connections. Analytical performance guarantees are established for random graph models. In sparse regimes, degree-biased sampling yields a higher expected matching size than prior communication-constrained algorithms; in denser settings, a counterintuitive phenomenon emerges where deliberately restricting available connections through thinning increases the expected number of matches. Combining thinning to degree two with greedy selection produces an algorithm that requires no parameter tuning and, in packet-level simulations with production traffic traces, significantly extends the network stability region. Although motivated by data center network scheduling, the underlying framework of bipartite matching under local information constraints is portable to other resource allocation settings. |
| title | Bipartite matching under communication constraints |
| topic | Distributed, Parallel, and Cluster Computing Networking and Internet Architecture |
| url | https://arxiv.org/abs/2604.10744 |