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]).
Type de document :
Rapport
[Research Report] Lirmm; Montpellier II. 2016
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01310648
Contributeur : Guillerme Duvillie <>
Soumis le : lundi 2 mai 2016 - 23:32:29
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 24 mai 2016 - 17:58:27

Fichier

ctw.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Partage selon les Conditions Initiales 4.0 International License

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

128

Téléchargements de fichiers

151