A proof of Parisi's conjecture on the random assignment problem
From MaRDI portal
Abstract: An assignment problem is the optimization problem of finding, in an m by n matrix of nonnegative real numbers, k entries, no two in the same row or column, such that their sum is minimal. Such an optimization problem is called a random assignment problem if the matrix entries are random variables. We give a formula for the expected value of the optimal k-assignment in a matrix where some of the entries are zero, and all other entries are independent exponentially distributed random variables with mean 1. Thereby we prove the formula 1+1/4+1/9+...+1/k^2 conjectured by G. Parisi for the case k=m=n, and the generalized conjecture of D. Coppersmith and G. B. Sorkin for arbitrary k, m and n.
The authors prove a formula for the expected value of the optimal \(k\)-assignment in a matrix where some of the entries are zero, and all the other entries are independent exponentially distributed random variables with mean 1. An assignment problem is the optimization problem of finding, in an \(m\)-by-\(n\) matrix of nonnegative real numbers, \(k\) entries, no two in the same row or column, such that their sum is minimal. In consequence, in the paper, the authors prove the Parisi's conjecture for the case \(k= m= n\), as well as the generalized conjecture of Coppersmith and Sorkin for arbitrary \(k\), \(m\), and \(n\).
Recommendations
- Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
- On the expected value of the minimum assignment
- scientific article; zbMATH DE number 1802784
- A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
- Constructive bounds and exact expectations for the random assignment problem
Cited in
(39)- The k-assignment polytope
- An easy proof of the \(\zeta (2)\) limit in the random assignment problem
- Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
- On random multi-dimensional assignment problems
- Random assignment problems on 2d manifolds
- Strong and weighted matchings in inhomogenous random graphs
- The planted matching problem: phase transitions and exact results
- Typical values of extremal-weight combinatorial structures with independent symmetric weights
- The stable marriage problem: an interdisciplinary review from the physicist's perspective
- Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
- A general method for lower bounds on fluctuations of random variables
- Local tail bounds for functions of independent random variables
- The Mézard-Parisi equation for matchings in pseudo-dimension \(d > 1\)
- Minimum cost matching in a random graph with random costs
- Distributionally robust mixed integer linear programs: persistency models with applications
- The blind passenger and the assignment problem
- Weight of a link in a shortest path tree and the Dedekind eta function
- Edge flows in the complete random-lengths network
- On the expected value of the minimum assignment
- Disproof of a conjecture on assignment functions
- Replica symmetry of the minimum matching
- On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
- A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
- The random fractional matching problem
- The effect of adding randomly weighted edges
- The minimum perfect matching in pseudo-dimension \(0<q<1\)
- Random-link matching problems on random regular graphs
- Efficient algorithms for three‐dimensional axial and planar random assignment problems
- On the number of \(k\)-cycles in the assignment problem for random matrices
- A survey of max-type recursive distributional equations
- Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
- The planted matching problem: sharp threshold and infinite-order phase transition
- The mean field traveling salesman and related problems
- Extrema of a multinomial assignment process
- Quick or cheap? Breaking points in dynamic markets
- A CLuP algorithm to practically achieve 0.76 SK-model ground state free energy
- Asymptotic results for random multidimensional assignment problems
- Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
- Random assignment problems
This page was built for publication: A proof of Parisi's conjecture on the random assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1434092)
