Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
osu1188445939.pdf (631.81 KB)
ETD Abstract Container
Abstract Header
Polyhedral structure of the K-median problem
Author Info
Zhao, Wenhui
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=osu1188445939
Abstract Details
Year and Degree
2007, Doctor of Philosophy, Ohio State University, Industrial and Systems Engineering.
Abstract
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.
Committee
Marc Posner (Advisor)
Pages
118 p.
Subject Headings
Operations Research
Keywords
facets,
;
polyhedral description
Recommended Citations
Refworks
EndNote
RIS
Mendeley
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)
Abstract Footer
Document number:
osu1188445939
Download Count:
579
Copyright Info
© 2007, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.