# The Circuit Polytope: Facets

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.

ZAIK Number: | zpr94-153 |
---|---|

Depositing User: | Archive Admin |

Date Deposited: | 02 Apr 2001 00:00 |

Last Modified: | 16 Nov 2011 11:11 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/153 |