Bauer, Petra (1997) The Circuit Polytope: Facets.
Published in: Mathematics of operations research Vol. 22 (1). pp. 110-145.

Abstract

Given an undirected graph G=(V,E) and a costs c(e) attached to the edges of G, the weighted girth problem is to find a circuit in G having minimum total cost. This problem is in general NP-hard since the traveling salesman problem can be reduced to it. A promising approach to hard combinatorial optimization problems is given by the so-called cutting plane methods. These involve linear programming techniques based on a partial description of the convex hull of the incidence vectors of possible solutions. We consider the weighted girth problem in the case where G is the complete graph and study the facial structure of the circuit polytope and some related polyhedra. In the appendix we give complete characterizations of some small circuit polytopes.

Actions:

Full text not available from this repository.

Editorial actions:	View Item (Login required)