Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

Polyhedral structure of the K-median problem

Zhao, Wenhui

Abstract Details

2007, Doctor of Philosophy, Ohio State University, Industrial and Systems Engineering.
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.
Marc Posner (Advisor)
118 p.

Recommended Citations

Citations

  • Zhao, W. (2007). Polyhedral structure of the K-median problem [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1188445939

    APA Style (7th edition)

  • Zhao, Wenhui. Polyhedral structure of the K-median problem. 2007. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1188445939.

    MLA Style (8th edition)

  • Zhao, Wenhui. "Polyhedral structure of the K-median problem." Doctoral dissertation, Ohio State University, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=osu1188445939

    Chicago Manual of Style (17th edition)