The minimum cover problem is a well-known NP complete one to choose a minimum number of column vectors from a matrix T = [tij], tij ∈ {1, 0}, satisfying the condition that any element of the sum of these column vectors is not zero. The corresponding relaxation problem is defined by replacing the sum with the weighted sum of column vectors, where the weight xj varies in a closed interval between 0 and 1. In this paper, the maximum matrix is newly defined, and a relation 0 ≤ k ≤ (n + 1) – 2√(n), where k is the maximum difference between the solution of the minimum cover problem and its relaxation one, and where n is the number of variables (column vectors), is proved to hold. A direct conclusion of this relation is that the minimum cover problem of at most three variables can be solved in a polynomial time because the corresponding relaxation problem has the polynomial time algorithm such as the interior point method.
