Geodesic
Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations
Discrete mathematics & theoretical computer science, FCT '15, Tome 19 (2017-2018) no. 4.

Voir la notice de l'article provenant de la source Episciences

In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called \BVA). 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. 
@article{DMTCS_2017_19_4_a3,
     author = {Bougeret, Marin and Duvilli\'e, Guillerme and Giroudeau, Rodolphe and Watrigant, R\'emi},
     title = {Multidimensional {Binary} {Vector} {Assignment} problem: standard, structural and above guarantee parameterizations},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {4},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-4-3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-4-3/}
}
TY  - JOUR
AU  - Bougeret, Marin
AU  - Duvillié, Guillerme
AU  - Giroudeau, Rodolphe
AU  - Watrigant, Rémi
TI  - Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-4-3/
DO  - 10.23638/DMTCS-19-4-3
LA  - en
ID  - DMTCS_2017_19_4_a3
ER  - 
%0 Journal Article
%A Bougeret, Marin
%A Duvillié, Guillerme
%A Giroudeau, Rodolphe
%A Watrigant, Rémi
%T Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-4-3/
%R 10.23638/DMTCS-19-4-3
%G en
%F DMTCS_2017_19_4_a3
Bougeret, Marin; Duvillié, Guillerme; Giroudeau, Rodolphe; Watrigant, Rémi. Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations. Discrete mathematics & theoretical computer science, FCT '15, Tome 19 (2017-2018) no. 4. doi : 10.23638/DMTCS-19-4-3. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-4-3/

Cité par Sources :