The integrality gap is the maximum ratio between the values of the optima of the integer program (IP) and of its LP relaxation.

The integrality gap is the maximum ratio between the values of the optima of the integer program (IP) and of its LP relaxation.

history | excerpt history