Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
type: Item
instance of: scholarly article
title: Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
zbMATH Open document ID: 1147.90033
author: Pavlo A. Krokhmal
author: Panos M. Pardalos
author: Don A. Grundel
published in: Mathematical Programming. Series A. Series B
publication date: 2007-03-05T00:00:00Z
review text: 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.
reviewed by: Matthias Ehrgott
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90B80
Mathematics Subject Classification ID: 90C15
Mathematics Subject Classification ID: 90C31
zbMATH DE Number: 5131078
zbMATH Keywords: multidimensional assignment problem
zbMATH Keywords: asymptotic analysis
zbMATH Keywords: expected optimal value
MaRDI profile type: Publication
full work available at URL: s10107-006-0036-x
OpenAlex ID: W2039142680
cites work: GRASP with path relinking for three-index assignment
cites work: Asymptotics in the random assignment problem
cites work: The \(\zeta(2)\) limit in the random assignment problem
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Solving the multisensor data association problem.
cites work: An Algorithm for the Three-Index Assignment Problem
cites work: On the Limit Behaviour of Extreme Order Statistics
cites work: Selected topics on assignment problems
cites work: Q3145800
cites work: APPLYING SIMULATED ANNEALING TO THE MULTIDIMENSIONAL ASSIGNMENT PROBLEM
cites work: Q3843209
cites work: Q5824493
cites work: General asymptotic expansions of Laplace integrals
cites work: Q4198056
cites work: A Lower Bound on the Expected Cost of an Optimal Assignment
cites work: On the number of local minima for the multidimensional assignment problem
cites work: Asymptotic properties of random multidimensional assignment problems
cites work: Q3780760
cites work: Certain expected values in the random assignment problem
cites work: A proof of Parisi's conjecture on the random assignment problem
cites work: Q4395333
cites work: Q4251080
cites work: Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
cites work: Q3126395
cites work: On the expected optimal value of random assignment problems: Experimental results and open questions
cites work: Letter to the Editor—The Multidimensional Assignment Problem
cites work: Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
cites work: Q4311918
cites work: Tracking elementary particles near their primary vertex: A combinatorial approach
cites work: On the Expected Value of a Random Assignment Problem
DOI: 10.1007/S10107-006-0036-X
description: scientific article; zbMATH DE number 5131078