Graph partitions for the multidimensional assignment problem

Chrysafis Vogiatzis (), Eduardo Pasiliao () and Panos Pardalos ()

Computational Optimization and Applications, 2014, vol. 58, issue 1, 205-224

Abstract: In this paper, we consider two decomposition schemes for the graph theoretical description of the axial Multidimensional Assignment Problem (MAP). The problem is defined as finding n disjoint cliques of size m with minimum total cost in K m×n , which is an m-partite graph with n elements per dimension. Even though the 2-dimensional assignment problem is solvable in polynomial time, extending the problem to include n≥3 dimensions renders it $\mathcal{NP}$ -hard. We propose two novel decomposition schemes for partitioning a MAP into disjoint subproblems, that can then be recombined to provide both upper and lower bounds to the original problem. For each of the partitioning schemes, we investigate and compare the efficiency of distinct exact and heuristic methodologies, namely augmentation and partitioning. Computational results for the methods, along with a hybrid one that consists of both partitioning schemes, are presented to depict the success of our approaches on large-scale instances. Copyright Springer Science+Business Media New York 2014

Keywords: Multidimensional assignment problem; Multi-sensor multi-target tracking problem; Graph decomposition; Parallel computing (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-013-9619-7 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:58:y:2014:i:1:p:205-224

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-013-9619-7

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().