Gilmore-Lawler bound (${\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.