pith. sign in

arxiv: 1403.3635 · v3 · pith:GFUQAG7Bnew · submitted 2014-03-14 · 🧮 math.CO · math.PR

The Minimum Perfect Matching in Pseudo-dimension 0<q<1

classification 🧮 math.CO math.PR
keywords costcostsedgematchingminimumperfectpseudo-dimensionapplicable
0
0 comments X
read the original abstract

It is known that for $K_{n,n}$ equipped with i.i.d. $exp(1)$ edge costs, the minimum total cost of a perfect matching converges to $\pi^2/6$ in probability. Similar convergence has been established for all edge cost distributions of pseudo-dimension $q \geq 1$, such as Wei(1,q) costs. In this paper we extend those results all $q>0$, confirming the M\'ezard-Parisi conjecture in the last remaining applicable case.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.