Polyhedral structure of the K-median problem

by 1973- Zhao, Wenhui

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. Key words and phrases: facets, polyhedral description ii This is dedicated to my parents, Lianyou Zhao and Jingzhi Wang, and my wife, Xiaoping Lang. iii