Approximability of a {0,1}-matrix Problem

Title
Approximability of a {0,1}-matrix Problem
Publication Date
2005-09
Author(s)
Brankovic, Ljiljana
( author )
OrcID: https://orcid.org/0000-0002-5056-4627
Email: lbrankov@une.edu.au
UNE Id une-id:lbrankov
Fernau, Henning
Editor
Editor(s): Joe Ryan, Prabhu Manyem, Kiki Sugeng and Mirka Miller
Type of document
Conference Publication
Language
en
Entity Type
Publication
Publisher
University of Ballarat
Place of publication
Ballarat, Australia
UNE publication id
une:1959.11/63391
Abstract

Weconsider the following combinatorial problem: given an n x m {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.
Link
link
Citation
Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005), p. 39-45
ISBN
0646452525
Start page
39
End page
45

Files:

NameSizeformatDescriptionLink