Structural study of the k-median problem

The past three decades have witnessed a tremendous growth in the literature on location problem. A mathematical formulation of uncapacitated plant location problem and the k-median as an integer program has proven very fruitful in the derivation of solution methods. Most of the successful algorithms for the problem are based on so-called ‘strong’ linear programming relaxation. This is due to the fact that the strong linear programming relaxation provides a tight lower bound. This paper investigates the phenomenon with a structural analysis of the problem.