A STATISTICAL-MECHANICS ANALYSIS OF THE SET COVERING PROBLEM

The dependence of the optimal solution average cost E(m) of the set co vering problem on the density of 1's of the incidence matrix (beta) an d on the number of constraints (P) is investigated in the limit where the number of items (N) goes to infinity. The annealed approximation i s employed to study two stochastic models: the constant density model, where the elements of the incidence matrix are statistically independ ent random variables, and the Karp model, where the rows of the incide nce matrix possess the same number of 1's. Lower bounds for E(m) are p resented in the case that P scales with ln N and beta is of order 1, a s well as in the case that P scales linearly with N and beta is of ord er 1/N. It is shown that in the case that P scales with exp N and beta is of order 1 the annealed approximation yields exact results for bot h models.