scientific article; zbMATH DE number 1802784
Let \(A\) be an \(m\times n\) matrix whose elements are i.i.d. random variables distributed exponentially with parameter 1. Let \(A^*= A^*(k,m,n)\) be the smallest sum of \(k\) elements of \(A\) where no two of them share a row or column, i.e. \(A^*\) is the cost of the minimum \(k\)-assignment of \(A\). For \(k= m= n\) we have the classical assignment problem. The authors study the conjecture \[ f(k,m,n)= EA^*= \sum_{i+ j< k}(m- i)^{-1}(n- j)^{-1}\tag{1} \] and related problems. For the classical problem this implies the conjecture \(f(n,n,n)= \sum_{i\leq n} i^2\). One also may see \(A^*\) as the minimum-cost cardinality-\(k\) matching in the complete bipartite graph \(K_{mn}\). A linear programming formulation is also given. The authors generalize this setting by allowing a set \(Z\subset K_{mn}\) with \(a(i,j)= 0\). Their main theorem, with the obvious definition of \(A^*(k,m,n,Z)\) runs as follows: Let there be \(R\subset K_{mn}\) such that \(R\cap Z=\emptyset\), \(| R\cap M|= s\) fixed for all matchings \(M\) in a certain class of matchings. Then \(A^*(k,m,n,Z)\) is distributed as \(A^*(k,m,n,Z\cup \{(i,j)\})\) plus an independent exponential. Here \((i,j)\) is chosen at random from \(R\). This promises a recurrence. By a dynamic programming algorithm, using this theorem, \(f(k,m,n)\) and \(\psi(k,m,n,t)= E(- t\exp(A^*(k,m,n)))\) are computed for \((k,m,n)= (2,3,3)\), \((3,4,4)\), \((4,5,5)\), \((5,5,6)\) and \((6,6,6)\), verifying (1). Section 5.5 describes a procedure to ``lift \(m\) and \(n\). In this way (1) is proved for \(k\leq 4\), \(m,n\geq k\) and for \(k= m= 5\), \(n\geq 5\). Further proofs are restricted by the misfortune that the above set \(R\) does not always exist. For the study of \(V(k,m,n)= \text{Var\,}A^*\) the authors define \(S(k,m,n,t)\) as a quotient of two products of Laplace transforms of exponentials. It is shown that \(S\) is the Laplace transform of a probability distribution whose expectation equals (1). Also \(S\) approximates but does not equal \(\psi\). It is conjectured that \(V(k,m,n)\) is equal to the variance corresponding to \(S\). Finally, the asymptotic behaviour and bounds of \(f(k,m,n)\) and \(V(k,m,n)\) are studied. In particular: \(nV(n,n,n)\geq 1\).
- Asymptotics in the random assignment problem
- On the expected optimal value of random assignment problems: Experimental results and open questions
- Certain expected values in the random assignment problem
- An assignment problem at high temperature
- A proof of Parisi's conjecture on the random assignment problem
- Probabilistic assignment: an extension approach
- The number of optimal matchings for Euclidean assignment on the line
- Maxima and near-maxima of a Gaussian random assignment field
- A general method for lower bounds on fluctuations of random variables
- On the maximum of random assignment process
- Asymptotic moments of the bottleneck assignment problem
- The blind passenger and the assignment problem
- On the expected value of the minimum assignment
- Random assignment and shortest path problems
- scientific article; zbMATH DE number 4043612 (Why is no real title available?)
- scientific article; zbMATH DE number 1263267 (Why is no real title available?)
- A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
- On the number of \(k\)-cycles in the assignment problem for random matrices
- Randomization with non-uniform allocations: fulfillment time distributions and bias properties
- ON THE FLUCTUATION IN THE RANDOM ASSIGNMENT PROBLEM
- ON THE RANDOM n×n ASSIGNMENT PROBLEM
- On the Maximum of a Special Random Assignment Process
- The mean field traveling salesman and related problems
- A simplified formula for quantification of the probability of deterministic assignments in permuted block randomization
- A CLuP algorithm to practically achieve 0.76 SK-model ground state free energy
- Random assignment problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3147236)
