Approximability and exact resolution of the Multidimensional Binary Vector Assignment problem
Abstract
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]).
Origin | Files produced by the author(s) |
---|
Loading...