Asymptotic behavior of the expected optimal value of the multidimensional assignment problem

DOI10.1007/s10107-006-0036-xzbMath1147.90033OpenAlexW2039142680MaRDI QIDQ868473

Panos M. Pardalos, Pavlo A. Krokhmal, Don A. Grundel

Publication date: 5 March 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0036-x

zbMATH Keywords

asymptotic analysismultidimensional assignment problemexpected optimal value

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Stochastic programming (90C15) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability, On finding \(k\)-cliques in \(k\)-partite graphs, Computational Studies of Randomized Multidimensional Assignment Problems, A new greedy algorithm for the quadratic assignment problem, On optimality of a polynomial algorithm for random linear multidimensional assignment problem, Maxima and near-maxima of a Gaussian random assignment field, Random assignment problems, Integer programming models for the multidimensional assignment problem with star costs, Local search heuristics for the multidimensional assignment problem, Efficient algorithms for three‐dimensional axial and planar random assignment problems, Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Selected topics on assignment problems
• General asymptotic expansions of Laplace integrals
• Asymptotic properties of random multidimensional assignment problems
• On the number of local minima for the multidimensional assignment problem
• Asymptotics in the random assignment problem
• On the expected optimal value of random assignment problems: Experimental results and open questions
• Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
• Certain expected values in the random assignment problem
• A proof of Parisi's conjecture on the random assignment problem
• Tracking elementary particles near their primary vertex: A combinatorial approach
• Solving the multisensor data association problem.
• The ?(2) limit in the random assignment problem
• GRASP with Path Relinking for Three-Index Assignment
• On the Expected Value of a Random Assignment Problem
• APPLYING SIMULATED ANNEALING TO THE MULTIDIMENSIONAL ASSIGNMENT PROBLEM
• An Algorithm for the Three-Index Assignment Problem
• A Lower Bound on the Expected Cost of an Optimal Assignment
• Letter to the Editor—The Multidimensional Assignment Problem
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• On the Limit Behaviour of Extreme Order Statistics