Back to search

University of Waterloo

On The Circuit Diameters of Some Combinatorial Polytopes

Abstract

dc:description.abstract

The combinatorial diameter of a polytope P is the maximum value of a shortest path between two vertices of P, where the path uses the edges of P only. In contrast to the combinatorial diameter, the circuit diameter of P is defined as the maximum value of a shortest path between two vertices of P, where the path uses potential edge directions of P i.e., all edge directions that can arise by translating some of the facets of P . In this thesis, we study the circuit diameter of polytopes corresponding to classical combinatorial optimization problems, such as the Matching polytope, the Traveling Sales- man polytope and the Fractional Stable Set polytope. We also introduce the notion of the circuit diameter of a formulation of a polytope P. In this setting the circuits are determined from some external linear system describing P which may not be minimal with respect to its constraints. We use this notion to generalize other results of this thesis, as well as introduce new results about a formulation of the Spanning Tree polytope and a formulation of the Matroid polytope.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kafer, Sean
Advisor dc:contributor.advisor
  • Sanità, Laura

Subjects

dc:subject × 11

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/12413

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kafer, Sean. On The Circuit Diameters of Some Combinatorial Polytopes. University of Waterloo, 2017. http://hdl.handle.net/10012/12413