|
|||||
|
|
Approximability and exact resolution of the multidimensional binary vector assignment problem |
||
| Authors: | Marin Bougeret Guillerme Duvillié Rodolphe Giroudeau | |
| Institution: | 1.LIRMM,Montpellier,France;2.Université libre de Bruxelles,Brussels,Belgium | |
| Abstract: | 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, \ldots , 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 Open image in new window c zeros by Open image in new window Open image in new windowOpen image in new window Open image in new window Open image in new window Open image in new window Open image in new windowOpen image in new windowOpen image in new windowOpen image in new windowOpen image in new windowOpen image in new windowOpen image in new windowOpen image in new windowOpen image in new windowOpen image in new window | |
| Keywords: | ||
| 本文献已被 SpringerLink 等数据库收录！ | ||