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