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.


Actions:
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
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/153