A Polynomial-Time Algorithm for Solving the Set Covering Problem on a Totally-Balanced Matrix

摘要

A (0,1) matrix that is totally balanced, i.e., it does not contain a square submatrix of size at least three which has no identical columns, and its row and column sums are equal to two, is considered. Let A be an nxm totally balanced matrix. An 0 ((minm,n) squared max m,n) algorithm is given to solve the set covering problem defined on A; a tree location problem serves as an example of such a set covering problem. An algorithm which recognizes an nxm totally balanced matrix (m or = N) in 0 (nm squared) time is also shown.