Approximability and exact resoltion of the Mutidimensional Binary Vector Assignment problem

JOCO Accepted

Journal - Journal of Combinatorial Optimization (2017)

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 $\min \sum 0$, and the restriction of this problem where every vector has at most $c$ zeros by $\left(\min \sum 0\right)_{\# 0 \leq c}$.

$\left(\min \sum 0\right)_{\# 0 \leq 2}$ was only known to be $\textbf{APX}$-complete, even for $m = 3$. We show that, assuming the unique games conjecture, it is $\textbf{NP}$-hard to $(n - \varepsilon)$-approximate $\left(\min \sum 0\right)_{\#0 \leq 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(\min \sum 0\right)_{\#0 \leq 1}$ is $\textbf{APX}$-complete even for $n = 2$.

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