Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/55344
Title: Multidimensional binary vector assignment problem : standard, structural and above guarantee parameterizations
Authors: Bougeret, M
Duvillié, G
Giroudeau, R
Watrigant, R
Issue Date: 2015
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
Abstract: In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called bMVA). An input of this problem is defined by m disjoint sets V1, V2,…, Vm, 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 Vi. 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. 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.
Description: 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015
URI: http://hdl.handle.net/10397/55344
ISBN: 9783319221762
ISSN: 0302-9743
EISSN: 1611-3349
DOI: 10.1007/978-3-319-22177-9_15
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

18
Last Week
4
Last month
Checked on Aug 14, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.