= Gilmore-Lawler bound
{c}
{title2=$\min_\pi\sum_i\ell_{i,\pi(i)}$}
For each facility $i$ and location $k$, independently minimize its row contribution over bijections from the other facilities to the other locations, giving $\ell_{ik}$. Every complete assignment has row contribution at least its corresponding $\ell_{ik}$, so minimizing their sum is a lower bound on the quadratic objective. Fixed assignments are retained as constraints in this <assignment problem>, which the <Hungarian algorithm> solves. The independently optimal rows need not be simultaneously realizable, explaining why the bound can be strict.
Back to article page
