Skip to Main content Skip to Navigation
Reports

Approximability and exact resolution of the Multidimensional Binary Vector Assignment problem

Marin Bougeret 1 Guillerme Duvillié 2 Rodolphe Giroudeau 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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]).
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01310648
Contributor : Guillerme Duvillie <>
Submitted on : Monday, May 2, 2016 - 11:32:29 PM
Last modification on : Thursday, June 11, 2020 - 8:56:02 PM
Long-term archiving on: : Tuesday, May 24, 2016 - 5:58:27 PM

File

ctw.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - ShareAlike 4.0 International License

Identifiers

  • HAL Id : lirmm-01310648, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

316

Files downloads

532