Title: Multi-dimensional vector assignment problems
Authors: Dokka, T ×
Crama, Y
Spieksma, Frits #
Issue Date: 2014
Publisher: Elsevier
Series Title: Discrete Optimization vol:14 pages:111-125
Abstract: We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by mm disjoint sets, each of which contains the same number nn of pp-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an mm-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the mm sets of vectors into nn mm-tuples so that no two vectors from the same set are in the same mm-tuple and so that the sum of the costs of the mm-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed mm. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case m=3m=3 and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension pp.
ISSN: 1572-5286
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
5 - TDokka_DOrevjuly2014 - YC.pdfMulti-dimensional vector assignment problems Published 959KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science