The Circuit Polytope: Facets

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


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr94-153
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Nov 2011 11:11