Approximability and exact resolution of the multidimensional binary vector assignment problem

In this paper we consider the multidimensional binary vector assignment problem. An input of this problem is defined by m disjoint multisets V1,V2,…,Vm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V^1, V^2, \ldots , V^m$$\end{document}, each composed of n binary vectors of size p. An output is a set of n disjoint m-tuples of vectors, where each m-tuple is obtained by picking one vector from each multiset Vi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V^i$$\end{document}. To each m-tuple we associate a p dimensional vector by applying the bit-wise AND operation on the m vectors of the tuple. The objective is to minimize the total number of zeros in these n vectors. We denote this problem by [inline-graphic not available: see fulltext], and the restriction of this problem where every vector has at most c zeros by [inline-graphic not available: see fulltext]. [inline-graphic not available: see fulltext] was only known to be [inline-graphic not available: see fulltext]-hard, even for [inline-graphic not available: see fulltext]. We show that, assuming the unique games conjecture, it is [inline-graphic not available: see fulltext]-hard to [inline-graphic not available: see fulltext]-approximate [inline-graphic not available: see fulltext] for any fixed [inline-graphic not available: see fulltext] and [inline-graphic not available: see fulltext]. This result is tight as any solution is a [inline-graphic not available: see fulltext]-approximation. We also prove without assuming UGC that [inline-graphic not available: see fulltext] is [inline-graphic not available: see fulltext]-hard even for [inline-graphic not available: see fulltext]. Finally, we show that [inline-graphic not available: see fulltext] is polynomial-time solvable for fixed [inline-graphic not available: see fulltext] (which cannot be extended to [inline-graphic not available: see fulltext]).