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.
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
(38)- Quick or cheap? Breaking points in dynamic markets
- On the expected value of the minimum assignment
- Edge flows in the complete random-lengths network
- Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
- Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
- Typical values of extremal-weight combinatorial structures with independent symmetric weights
- A survey of max-type recursive distributional equations
- On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
- Replica symmetry of the minimum matching
- Distributionally robust mixed integer linear programs: persistency models with applications
- The mean field traveling salesman and related problems
- A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
- Local tail bounds for functions of independent random variables
- Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
- An easy proof of the \(\zeta (2)\) limit in the random assignment problem
- The k-assignment polytope
- Random assignment problems on 2d manifolds
- On the number of \(k\)-cycles in the assignment problem for random matrices
- Random assignment problems
- A general method for lower bounds on fluctuations of random variables
- Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
- The planted matching problem: sharp threshold and infinite-order phase transition
- Extrema of a multinomial assignment process
- The random fractional matching problem
- The Mézard-Parisi equation for matchings in pseudo-dimension \(d > 1\)
- Minimum cost matching in a random graph with random costs
- The effect of adding randomly weighted edges
- The blind passenger and the assignment problem
- Strong and weighted matchings in inhomogenous random graphs
- Weight of a link in a shortest path tree and the Dedekind eta function
- On random multi-dimensional assignment problems
- Disproof of a conjecture on assignment functions
- The stable marriage problem: an interdisciplinary review from the physicist's perspective
- The planted matching problem: phase transitions and exact results
- Random-link matching problems on random regular graphs
- The minimum perfect matching in pseudo-dimension \(0<q<1\)
- Asymptotic results for random multidimensional assignment problems
- Efficient algorithms for three‐dimensional axial and planar 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)
