Polyhedral structure of the K-median problem
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 facet-defining, 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.
School:The Ohio State University
School Location:USA - Ohio
Source Type:Master's Thesis
Keywords:facets polyhedral description
Date of Publication:01/01/2007