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, V 2,..., V m, each composed of n binary vectors of size p. An output is a set of n disjointm- tuples of vectors, where each m- tuple is obtained by picking one vector from each multiset Vi. 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 min 0, and the restriction of this problem where every vector has at most c zeros by min 0 # 0=c. min 0 # 0=2 was only known to be APX- hard, even for m =3. We show that, assuming the unique games conjecture, it is NP- hard to ( n- e)- approximate min 0 # 0=1 for any fixed n and e. This result is tight as any solution is a n- approximation. We also prove without assuming UGC that min 0 # 0=1 is APX- hard even for n =2. Finally, we show that min 0 # 0=1 is polynomial- time solvable for fixed m ( which cannot be extended to min 0 # 0=2).