Approximability of a {0,1}-matrix Problem

Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/63391

Title:	Approximability of a {0,1}-matrix Problem
Contributor(s):	Brankovic, Ljiljana (author) ; Fernau, Henning (author)
Publication Date:	2005-09
Handle Link:	https://hdl.handle.net/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.
Publication Type:	Conference Publication
Conference Details:	AWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms, Ballarat, Australia, 18th - 21st September, 2005
Grant Details:	ARC/DP0452182
Source of Publication:	Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005), p. 39-45
Publisher:	University of Ballarat
Place of Publication:	Ballarat, Australia
Fields of Research (FoR) 2020:	490404 Combinatorics and discrete mathematics (excl. physical combinatorics) 460402 Data and information privacy
Socio-Economic Objective (SEO) 2020:	280115 Expanding knowledge in the information and computing sciences 220405 Cybersecurity
Peer Reviewed:	Yes
HERDC Category Description:	E1 Refereed Scholarly Conference Publication
Appears in Collections:	Conference Publication School of Science and Technology

2 files

File	Description	Size	Format

Show full item record

Check

Research UNE