Publications List

Approximability and exact resoltion of the Mutidimensional Binary Vector Assignment problem (JOCO 2017)
Marin Bougeret Guillerme Duvillié 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}$).
Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations (DMTCS 2017)
Marin Bougeret Guillerme Duvillié Rodolphe Giroudeau Rémi Watrigant
In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called $\textbf{bMVA}$). An input of this problem is defined by $m$ disjoint sets $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 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. mBVA can be seen as a variant of multidimensional matching where hyperedges are implicitly locally encoded via labels attached to vertices, but was originally introduced in the context of integrated circuit manufacturing. We provide for this problem FPT algorithms and negative results ($ETH$-based results, $W$[2]-hardness and a kernel lower bound) according to several parameters: the standard parameter $k$ i.e. the total number of zeros), as well as two parameters above some guaranteed values.
On the complexity of Wafer-to-Wafer Integration (DO 2016)
In this paper we consider the Wafer-to-Wafer Integration problem. A wafer can be seen as a $p$-dimensional binary vector. The input of this problem is described by $m$ multisets (called “lots”), where each multiset contains $n$ wafers. The output of the problem is a set of $n$ disjoint stacks, where a stack is a set of $m$ wafers (one wafer from each lot). To each stack we associate a $p$-dimensional binary vector corresponding to the bit-wise AND operation of the wafers of the stack. The objective is to maximize the total number of “$1$” in the $n$ stacks. We provide $m^{1−\varepsilon}$ and $p^{1−\varepsilon}$ non-approximability results even for $n=2$, $f(n)$ non-approximability for any polynomial-time computable function $f$, as well as a $\frac{p}{r}$-approximation algorithm for any constant $r$. Finally, we show that the problem is **FPT** when parameterized by $p$, and we use this **FPT** algorithm to improve the running time of the $\frac{p}{r}$-approximation algorithm.
Approximability and Exact Resolution of the Multidimensional Binary Vector Assignment Problem (ISCO 2016 2016)
Marin Bougeret Guillerme Duvillié 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}$).
Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations (FCT'15 2016)
In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called $\textbf{bMVA}$). An input of this problem is defined by m disjoint sets $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 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. $\textbf{bMVA}$ can be seen as a variant of multidimensional matching where hyperedges are implicitly locally encoded via labels attached to vertices, but was originally introduced in the context of integrated circuit manufacturing. We provide for this problem FPT algorithms and negative results (ETH-based results, $W$[2]-hardness and a kernel lower bound) according to several parameters: the standard parameter $k$ (i.e. the total number of zeros), as well as two parameters above some guaranteed values.
On the complexity of Wafer-to-Wafer Integration (CIAC'15 2015)
In this paper we consider the Wafer-to-Wafer Integration problem. A wafer is a $p$-dimensional binary vector. The input of this problem is described by $m$ disjoints sets (called “lots”), where each set contains $n$ wafers. The output of the problem is a set of $n$ disjoint stacks, where a stack is a set of $m$ wafers (one wafer from each lot). To each stack we associate a $p$-dimensional binary vector corresponding to the bit-wise AND operation of the wafers of the stack. The objective is to maximize the total number of “1” in the $n$ stacks. We provide $O(m^{1-\epsilon })$ and $O(p^{1-\epsilon })$ non-approximability results even for $n= 2$, as well as a $\frac{p}{r}$-approximation algorithm for any constant $r$. Finally, we show that the problem is FPT when parameterized by $p$, and we use this FPT algorithm to improve the running time of the $\frac{p}{r}$-approximation algorithm.
Scheduling fixed tasks while maximizing the minimum idle interval via Precoloring Extension on unit interval graphs (MAPSP'15 2015)
Marin Bougeret Guillerme Duvillié Rodolphe Giroudeau
In this paper, we consider an hotel booking management problem motivated by the following situation. Consider an hotel with m rooms. Suppose that the booking management system already accepted $n_r$ future reservations (where each reservation $r_l$ requires one room between a starting time $s(r_l)$ and an end date $d(r_l)$, i.e. the system attributed a room for each reservation, without overlap. Now, suppose that $n_t$ new reservations are submitted. Our objective in this paper is to accept these $n_t$ reservations while maximizing the size of the minimum idle period (where an idle period is an unoccupied room). We show that problem is $\textbf{NP}$-hard from a reduction from Precoloring Extension on unit interval graphs ($\textbf{PreExt}$). We also highlight a reduction from $\textbf{PreExt}$ to our problem proving that the letter is FPT when parameterized by the number of machines. We provide an ad hoc dynamic programming algorithm which also runs in time FPT when parameterized by $m$ and a $2$-dual approximation algorithm.