Asymptotic Results for Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is an NP-hard combinatorial optimization problem occurring in applications such as data association and target tracking. In this paper, we investigate characteristics of the mean optimal solution values for random MAPs with axial constraints. Throughout...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2005-07, Vol.31 (3), p.275-293
Main Authors: Grundel, Don, Oliveira, Carlos A S, Pardalos, Panos M, Pasiliao, Eduardo
Format: Article
Language:English
Subjects:
Algorithms
Assignment problem
Combinatorial analysis
Costs
Curve fitting
Distribution costs
Estimating techniques
Expected values
Experiments
Mathematical models
Numerical prediction
Operations research
Optimization
Studies
Tracking
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The multidimensional assignment problem (MAP) is an NP-hard combinatorial optimization problem occurring in applications such as data association and target tracking. In this paper, we investigate characteristics of the mean optimal solution values for random MAPs with axial constraints. Throughout the study, we consider cost coefficients taken from three different random distributions: uniform, exponential and standard normal. In the cases of uniform and exponential costs, experimental data indicates that the mean optimal value converges to zero when the problem size increases. We give a short proof of this result for the case of exponentially distributed costs when the number of elements in each dimension is restricted to two. In the case of standard normal costs, experimental data indicates the mean optimal value goes to negative infinity with increasing problem size. Using curve fitting techniques, we develop numerical estimates of the mean optimal value for various sized problems. The experiments indicate that numerical estimates are quite accurate in predicting the optimal solution value of a random instance of the MAP.
ISSN:0926-6003
1573-2894
DOI:10.1007/s10589-005-3227-0