@article {IOPORT.01051139,
    author       = {German, O.V.},
    title        = {Resolution principle for the minimum covering problem of a 0-1 matrix.},
    year         = {1996},
    journal      = {Cybernetics and Systems Analysis},
    volume       = {32},
    number       = {1},
    issn         = {1060-0396},
    pages        = {111-119 (1996); translation from Kibern. Sist. Anal. 1996, No. 1, 135-146},
    publisher    = {Springer (Consultants Bureau), New York, NY},
    doi          = {10.1007/BF02366588},
    abstract     = {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.},
    identifier   = {01051139},
}