Strengthening the integrality gap for the capacitated facility location problem with LP-based rounding algorithms

This thesis studies the capacitated facility location problem, in which all clients have unit demand and all facilities have integral capacity. A linear relaxation is researched, with corresponding integrality gap bounded by a constant. Recently, such a linear relaxation has been found and proven using an LP-bounding algorithm. The formulation...