Moment generating functions in combinatorial optimization: Bipartite matching
Johan Wästlund · 2026
Read Moment generating functions in combinatorial optimization: Bipartite matching by Johan Wästlund (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-07563.txt.
Description
In a random model of minimum-cost bipartite matching with exponential edge costs, the optimal cost's spread turns out to be computable. Johan Wästlund shows that spread is captured by its moment generating function, which in this model is always rational.
The complex zeros of that function matter: no zeros near the origin signals regularity of the spread. The paper conjectures those functions never have complex zeros of smaller modulus than their first pole, which for the assignment problem would imply a Gaussian scaling limit. Combinatorial optimizers get an efficient distributional computation plus a precise claim linking zeros to limit laws.
Catalog record
| CREATOR | Johan Wästlund |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-07563