A note on the polytope of bipartite TSP

Kovács, Gergely and Tuza, Zsolt and Vizvári, B. and Jabbari, H.K. (2018) A note on the polytope of bipartite TSP. DISCRETE APPLIED MATHEMATICS, 235. pp. 92-100. ISSN 0166-218X

Preview

Text 1703.10821v1.pdf Download (123kB) | Preview

Abstract

The main result of this paper is that the polytope of the bipartite TSP is significantly different from that of the general TSP. Comb inequalities are known as facet defining ones in the general case. In the bipartite case, however, many of them are satisfied whenever all degree and subtour elimination constraints are satisfied, i.e. these comb inequalities are not facet defining. The inequalities in question belong to the cases where vertices of one of the two classes occur in less than the half of the intersections of the teeth and the hand. Such side conditions are necessary, as simple example shows that the comb inequality can be violated when each class has vertices in more than the half of the intersections. © 2017 Elsevier B.V.

Actions (login required)

Edit Item