Approximability of a {0,1} - matrix problem
Ljiljana Branković, Henning Fernau · Figshare · 2005
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.