Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
The multidimensional assignment problem is a generalisation of the linear assignment problem. It is to find \(n\) \(d\)-tupels from \(d\) sets of cardinality \(n\) so as to minimize the total cost of the tupels. In this paper the asymptotic behaviour of the expected optimal value \(Z_{d,n}^*\) of the multidimensional assignment problem is studied when the assignment costs are independent identically distributed random variables with an absolutely continuous distribution \(F\) with existing first moment. The main result is that for \(d\geq 3\), \(n\geq 2\) and \((a, b)\) the (finite or infinite) interior of the support set of \(F\) then \(Z_{d,n}^* \to na\) as \(n\to \infty\) or \(d \to \infty\), if some other conditions are satisfied. Furthermore, the authors prove asymptotic bounds on the value of \(Z_{d,n}^*\) and and present some numerical experiments for exponential and uniform distributions of costs.
- Asymptotic results for random multidimensional assignment problems
- Asymptotic properties of random multidimensional assignment problems
- scientific article; zbMATH DE number 2190116
- On the number of local minima for the multidimensional assignment problem
- Solving the multidimensional assignment problem by a cross-entropy method
- A Lower Bound on the Expected Cost of an Optimal Assignment
- A proof of Parisi's conjecture on the random assignment problem
- An Algorithm for the Three-Index Assignment Problem
- APPLYING SIMULATED ANNEALING TO THE MULTIDIMENSIONAL ASSIGNMENT PROBLEM
- Asymptotic properties of random multidimensional assignment problems
- Asymptotics in the random assignment problem
- Certain expected values in the random assignment problem
- General asymptotic expansions of Laplace integrals
- GRASP with path relinking for three-index assignment
- scientific article; zbMATH DE number 994432 (Why is no real title available?)
- scientific article; zbMATH DE number 6118218 (Why is no real title available?)
- scientific article; zbMATH DE number 4043612 (Why is no real title available?)
- scientific article; zbMATH DE number 1194779 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1304348 (Why is no real title available?)
- scientific article; zbMATH DE number 679871 (Why is no real title available?)
- scientific article; zbMATH DE number 1163720 (Why is no real title available?)
- scientific article; zbMATH DE number 3083637 (Why is no real title available?)
- Letter to the Editor—The Multidimensional Assignment Problem
- Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
- On the expected optimal value of random assignment problems: Experimental results and open questions
- On the Expected Value of a Random Assignment Problem
- On the Limit Behaviour of Extreme Order Statistics
- On the number of local minima for the multidimensional assignment problem
- Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
- Selected topics on assignment problems
- Solving the multisensor data association problem.
- The (2) limit in the random assignment problem
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Tracking elementary particles near their primary vertex: A combinatorial approach
- Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability
- Order statistics and the linear assignment problem
- On the expected optimal value of random assignment problems: Experimental results and open questions
- Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
- The constant objective value property for multidimensional assignment problems
- A new greedy algorithm for the quadratic assignment problem
- On random multi-dimensional assignment problems
- Solving the multidimensional assignment problem by a cross-entropy method
- Asymptotics of the optimum in discrete sequential assignment
- Maxima and near-maxima of a Gaussian random assignment field
- Integer programming models for the multidimensional assignment problem with star costs
- A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability
- The assignment problem with nearly Monge arrays and incompatible partner indices
- On finding \(k\)-cliques in \(k\)-partite graphs
- Efficient algorithms for three‐dimensional axial and planar random assignment problems
- Computational studies of randomized multidimensional assignment problems
- Local search heuristics for the multidimensional assignment problem
- scientific article; zbMATH DE number 2190116 (Why is no real title available?)
- Extrema of a multinomial assignment process
- On optimality of a polynomial algorithm for random linear multidimensional assignment problem
- Asymptotic results for random multidimensional assignment problems
- Asymptotic properties of random multidimensional assignment problems
- Random assignment problems
This page was built for publication: Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868473)
