Polyhedral structure of the K-median problem
Wenhui Zhao · OhioLink ETD Center (Ohio Library and Information Network) · 2007
The polyhedral structure of the K-median problem is examined.We present an extended formulation that has an integral polytope.Then, a set of extra variables are projected out and we obtain a reduced extended formulation.Based on the reduced formulation, we develop two basic properties for facets of K-median problem.By applying the two properties, we establish a class of 1-cover inequalities are facetdefining, and generalize three known classes of facets, de Vries facets, de Farias facets, and W -2 facets.For K = n -2, we project out the remainder extra variables from the reduced extended formulation and obtain a minimal complete description of the polytope.Finally, we extend the equality constraints for the 2-median problem developed by Goemans when the underlying graph is an undirected tree.