Hupp L, Liers F (2013)
Publication Status: Published
Publication Type: Journal article, Original article
Publication year: 2013
Publisher: Elsevier BV
Book Volume: 41
Pages Range: 213-220
DOI: 10.1016/j.endm.2013.05.095
Given an edge-weighted graph G= (V, E), the Hamiltonian p-median problem (HpMP) asks for determining p cycles in G whose total length is minimized such that each node is contained in exactly one cycle. As the travelling salesman problem (TSP) corresponds to the choice p= 1, the HpMP can be interpreted as a generalization of the TSP. In this paper, we study the polytope associated with the HpMP. To this end, we investigate several known classes of valid inequalities with respect to their facet inducing properties. Furthermore, we show that a subset of the well-known 2-matching inequalities from the TSP define facets of the Hamiltonian p-median polytope. © 2013 Elsevier B.V.
APA:
Hupp, L., & Liers, F. (2013). A polyhedral study of the Hamiltonian p-median problem. Electronic Notes in Discrete Mathematics, 41, 213-220. https://dx.doi.org/10.1016/j.endm.2013.05.095
MLA:
Hupp, Lena, and Frauke Liers. "A polyhedral study of the Hamiltonian p-median problem." Electronic Notes in Discrete Mathematics 41 (2013): 213-220.
BibTeX: Download