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 |