- Title
- Approximability of a {0,1} - matrix problem
- Creator
- Brankovic, Ljiljana; Fernau, Henning
- 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
- Publisher
- University of Ballarat, School of Information Technology and Mathematical Sciences
- Resource Type
- conference paper
- Date
- 2005
- 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.
- Subject
- {0,1}-matrix; combinatorial; approximability; NP-hard minimization; bipartite graphs
- Identifier
- http://hdl.handle.net/1959.13/32298
- Identifier
- uon:2987
- Identifier
- ISBN:0646452525
- Language
- eng
- Full Text
- Reviewed
- Hits: 1071
- Visitors: 1315
- Downloads: 281
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Publisher version (open access) | 440 KB | Adobe Acrobat PDF | View Details Download |