Polyhedral structure of the K-median problem

by Zhao, Wenhui

Abstract (Summary)
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.
Bibliographical Information:


School:The Ohio State University

School Location:USA - Ohio

Source Type:Master's Thesis

Keywords:facets polyhedral description


Date of Publication:01/01/2007

© 2009 All Rights Reserved.