Multi-Dimensional Vector Assignment Problems

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 m disjoint sets, each of which contains the same number n of p-dimensional
vectors with nonnegative integral components, and a cost function defined on vectors.
The cost of an m-tuple of vectors is defined as the cost of their component-wise maximum.
The problem is now to partition the m sets of vectors into n m-tuples so that no two
vectors from the same set are in the same m-tuple and so that the sum of the costs of the m-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 m. 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 = 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 p.