gap of 4/3. Typically, the integrality gap translates into the approximation ratio of an approximation algorithm. This is because an approximation algorithm relies on some rounding strategy that finds, for every relaxed solution of size , an integer solution of size at most (where RR is the rounding ratio). If there is an instance with integrality gap IG, then every rounding strategy will return, on that instance, a rounded solution of size at least . Therefore necessarily . The rounding ratio RR is only an upper bound on the approximation ratio, so in theory the actual approximation ratio may be lower than IG, but this may be hard to prove. In practice, a large IG usually implies that the approximation ratio in the linear programming relaxation might be bad, and it may be better to look for other approximation schemes for that problem. For the set cover problem, Lovász proved that the integrality gap for an instance with n elements is Hn, the nth harmonic number. One can turn the linear programming relaxation for this problem into an approximate solution of the original unrelaxed set cover instance via the technique of randomized rounding . Given a fractional cover, in which each set Si has weight wi, choose randomly the value of each 0–1 indicator variable xi to be 1 with probability wi × (ln n +1), and 0 otherwise. Then any element ej has probability less than 1/(e×n) of remaining uncovered, so with constant probability all elements are covered. The cover generated by this technique has total size, with high probability, (1+o(1))(ln n)W, where W is the total weight of the fractional solution. Thus, this technique leads to a randomized approximation algorithm that finds a set cover within a logarithmic factor of the optimum. As showed, both the random part of this algorithm and the need to construct an explicit solution to the linear programming relaxation may be eliminated using the method of conditional probabilities, leading to a deterministic greedy algorithm for set cover, known already to Lovász, that repeatedly selects the set that covers the largest possible number of remaining uncovered elements. This greedy algorithm approximates the set cover to within the same Hn factor that Lovász proved as the integrality gap for set cover. There are strong complexity-theoretic reasons for believing that no polynomial time approximation algorithm can achieve a significantly better approximation ratio . Similar randomized rounding