Moment generating functions in combinatorial optimization: Bipartite matching
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912887604248576 |
|---|---|
| author | Wästlund, Johan |
| author_facet | Wästlund, Johan |
| contents | In a random model of minimum cost bipartite matching based on exponentially distributed edge costs, we show that the distribution of the cost of the optimal solution can be computed efficiently. The distribution is represented by its moment generating function, which in this model is always a rational function. The complex zeros of this function are of interest as the lack of zeros near the origin indicates a certain regularity of the distribution. We propose a conjecture according to which these moment generating functions never have complex zeros of smaller modulus than their first pole. For minimum cost perfect matching, also known as the assignment problem, such a zero-free disk would imply a Gaussian scaling limit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07563 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Moment generating functions in combinatorial optimization: Bipartite matching Wästlund, Johan Probability Discrete Mathematics 60C05, 90C27, 90C35 (Primary) In a random model of minimum cost bipartite matching based on exponentially distributed edge costs, we show that the distribution of the cost of the optimal solution can be computed efficiently. The distribution is represented by its moment generating function, which in this model is always a rational function. The complex zeros of this function are of interest as the lack of zeros near the origin indicates a certain regularity of the distribution. We propose a conjecture according to which these moment generating functions never have complex zeros of smaller modulus than their first pole. For minimum cost perfect matching, also known as the assignment problem, such a zero-free disk would imply a Gaussian scaling limit. |
| title | Moment generating functions in combinatorial optimization: Bipartite matching |
| topic | Probability Discrete Mathematics 60C05, 90C27, 90C35 (Primary) |
| url | https://arxiv.org/abs/2602.07563 |