In this paper we consider the multidimensional binary vector assignment problem. An input of this problem is dened by m disjoint sets V 1 , V 2 ,. .. , V m , 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 set V i. 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-complete, even for m = 3 [5]. We show that, assuming the unique games conjecture, it is NP-hard to (n − ε)-approximate (min 0) #0≤1 for any xed n and ε. This result is tight as any solution is a n-approximation. We also prove without assuming UGC that (min 0) #0≤1 is APX-complete even for n = 2, and we provide an example of n − f (n, m)-approximation algorithm for min 0. Finally, we show that (min 0) #0≤1 is polynomial-time solvable for xed m (which cannot be extended to (min 0) #0≤2 according to [5]).