One version of the group resolution principle for discrete optimization

Abstract

One modification of the group resolution principle (grp) to find a minimum-weighted covering set of 0,1-matrix is presented. The modification makes it possible to use grp in the same way both for non-weighted case of a minimumsize covering problem and for the weighted case. This enables one to use the single algorithm for the generalized covering problem. It is also shown how to modify the existing approach to avoid matrix sizes growing when adding new group resolvents at the iterations of the algorithm. The suggested technique is characterized by quite good computational complexity estimation showing the polynomial complexity of the method. Summarizing all this up, one can conclude that the method may find use for different optimization problems widely presented in data and text mining and the other areas.