Approximability and exact resolution of the Multidimensional Binary Vector Assignment problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Reports (Research Report) Year : 2016

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]).
Fichier principal
Vignette du fichier
ctw.pdf (404.29 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01310648 , version 1 (02-05-2016)

Licence

Identifiers

  • HAL Id : lirmm-01310648 , version 1

Cite

Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau. Approximability and exact resolution of the Multidimensional Binary Vector Assignment problem. [Research Report] Lirmm; Montpellier II. 2016. ⟨lirmm-01310648⟩
191 View
327 Download

Share

More