01051139

j

01051139 German, O.V. Resolution principle for the minimum covering problem of a 0-1 matrix. Cybern. Syst. Anal. 32, No.1, 111-119 (1996); translation from Kibern. Sist. Anal. 1996, No.1, 135-146 (1996). 1996 Springer (Consultants Bureau), New York, NY EN group resolution principle minimum covering problem 0-1 matrix

doi:10.1007/BF02366588

Summary: We consider the so-called group resolution principle (g.r.p.) for the minimum covering problem (MCP) and the weighted minimum covering problem (WMCP) of a 0-1 matrix. According to the g.r.p., the solution is sought similarly to deductive derivation in first-order logic. The convergence in probability to the optimal solution is accomplished by a polynomial-time algorithm. The present article provides a theoretical justification of the g.r.p. that substantially broadens its scope. The g.r.p. is shown to be polynomial on average for the MCP (WMCP). More rigorously, suppose that we seek a covering with $k$ or fewer rows for the MCP. If such a covering exists, then the g.r.p. will find it on average after $O(NM^2)$ iterations, where $N$ is the number of rows and $M$ is the number of columns in the original 0-1 matrix. If no such covering exists, then in general the g.r.p. requires exponential time to establish its nonexistence. However, in this case, we can also apply a previous result of the author which provides a bound for the number of coverings of the required size in a matrix. Due to this result, iterations can be stopped when the corresponding bound falls inside the confidence interval, i.e., the probability of existence of a covering of the required cardinality (size) becomes very small. This takes on average $O(NMp/\sqrt{1- p})$ iterations, where $p$ is the density (frequency) of $1s$ in the matrix. Our result demonstrates the practical advantages of the g.r.p., e.g., compared to Balas' algorithm, which is exponential on average. We have carried out a fairly thorough testing of the g.r.p.: some 600 problems have been solved by the statistically exact algorithm and 100 problems by the exact algorithm. Of the 600 problems on $N\times M$ matrices with $N\subset [40\text{-}100]$, $M\subset [40\text{-}150]$, the g.r.p.-based statistically exact algorithm found an exact solution in 592 cases in 0.4-10 sec per problem on an IBM PC/AT 386. The solution time for the exact algorithm with an a priori known minimum covering was even better than the above-mentioned analytical bound. Thus, the g.r.p. is justified both theoretically and practically.