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

CREATORJohan Wästlund
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-07563

Browse the full library · About the Tower of Babel