The integrality gap of a minimization problem with nonnegative objective values and a fixed optimization
relaxation is the supremum, over instances, of the
ratio of the original optimum to the relaxed optimum. For
instances 
with positive relaxed optimum 
, it is
 |
If the relaxed optimum is 0 and the original optimum is positive, the gap is 
.
For positive relaxed optima, each ratio
is at least 1 and measures the loss that can be hidden by fractional solutions (Williamson
and Shmoys 2011, Definition 5.13). For example, minimizing an integer 
subject to 
gives optimum 1, while allowing real 
gives optimum 
. This instance has ratio 2. For
a maximization problem, the ratio is often reversed so
that the gap is at least 1. The optimum-over-relaxation convention instead gives
a quantity at most 1.
An integrality gap constrains guarantees proved by comparing a feasible solution directly with the relaxed optimum. The Goemans-Linial relaxation of uniform sparsest cut is a graph-theoretic example.
