Approximability and Exact Resolution of the Multidimensional Binary Vector Assignment Problem

ISCO 2016 p. 148 - 159

International conference with proceedings - Proceedings ISCO 2016 (2016)

Authors: Marin Bougeret and Guillerme Duvillié and Rodolphe Giroudeau

In this paper we consider the multidimensional binary vector assignment problem. An input of this problem is defined by $m$ disjoint multisets $V^1, V^2, \dots , 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 multiset $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 $\mathrm{min}\sum 0$, and the restriction of this problem where every vector has at most $c$ zeros by $\left( \mathrm{min}\sum 0\right)_{\#0 \le c}$.

$\left( \mathrm{min}\sum 0\right)_{\#0 \le 2}$ was only known to be $\textbf{APX}$-complete, even for $m = 3$. We show that, assuming the unique games conjecture, it is ${\mathbf{NP}}$-hard to $(n- \varepsilon )$-approximate $\left( \mathrm{min}\sum 0\right)_{\#0 \le 1}$ for any fixed $n$ and $\varepsilon$. This result is tight as any solution is a $n$-approximation. We also prove without assuming UGC that $\left( \mathrm{min}\sum 0\right)_{\#0 \le 1}$ is $\textrm{APX}$-complete even for $n = 2$, and we provide an example of $n-f(n,m)$-approximation algorithm for $\mathrm{min}\sum 0$.

Finally, we show that $\left( \mathrm{min}\sum 0\right)_{\#0 \le 1}$ is polynomial-time solvable for fixed $m$ (which cannot be extended to $\left( \mathrm{min}\sum 0\right)_{\#0 \le 2}$).