Approximability of a {0,1}-matrix Problem

Author(s)
Brankovic, Ljiljana
Fernau, Henning
Publication Date
2005-09
Abstract
<p>Weconsider the following combinatorial problem: given an <i>n</i> x <i>m</i> {0,1}-matrix M, find a minimum cardinality set S of mergings between neighboring rows or columns that yields an all-zeros matrix. Here, merging means performing a component-wise AND operation. We prove that this NP-hard minimization problem is factor-2-approximable by relating it to the VERTEX COVER problem on bipartite graphs.</p>
Citation
Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005), p. 39-45
ISBN
0646452525
Link
https://hdl.handle.net/1959.11/63391
Language
en
Publisher
University of Ballarat
Title
Approximability of a {0,1}-matrix Problem
Type of document
Conference Publication
Entity Type
Publication

Files:

NameSizeformatDescriptionLink