Linear programming relaxation is a standard technique for designing approximation algorithms for hard optimization problems. In this application, an important concept is the integrality gap, the maximum ratio between the solution quality of the integer program and of its relaxation. In an instance of a minimization problem, if the real minimum (the minimum of the integer problem) is formula_6, and the relaxed minimum (the minimum of the linear programming relaxation) is formula_7, then the integrality gap of that instance is formula_8. In a maximization problem the fraction is reversed. The integrality gap is always at least 1. In the example above, the instance "F" = shows an integrality gap of 4/3.