Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/32298
- Title
- Approximability of a {0,1} - matrix problem
- Author/Creator
-
Brankovic, Ljiljana;
Fernau, Henning
- Description
- We consider the following combinatorial problem: given an n x m {0,1}-matrix M, find a minimum cardinality set S of meanings 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.
- Relation
- 16th Australasian Workshop on Combinatorial Algorithms (AWOCA 2005). Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005) (Ballarat, Vic. 18-21 September, 2005) p. 39-45
- Relation
- http://www.ballarat.edu.au/conferences/awoca2005
- Date
- 2005
- Publisher
- University of Ballarat, School of Information Technology and Mathematical Sciences
- Keyword(s)
-
{0,1}-matrix;
combinatorial;
approximability;
NP-hard minimization;
bipartite graphs
- Resource Type
- conference paper
- Identifier
- http://hdl.handle.net/1959.13/32298
- Identifier
- ISBN:0646452525
- Reviewed
- Full Text
-
-
40 Visitors
46 Hits
4 Downloads
