Cyclic transversal polytopes

Abstract

In der Literatur wurden klassische kombinatorische Optimierungsprobleme wie das Max- Cut-Problem oder das Stable-Set-Problem, ersatzweise auch die dazu gehörigen Cut- und Stable-Set-Polytope, bereits vielfach behandelt und diskutiert. Diese Arbeit bietet einen vereinheitlichten Blick auf diese beiden und andere Probleme. Die hier untersuchten Probleme lassen sich mit Hilfe ausgewählter Tupel von Binärvektoren beschreiben, deren Summe eine Paritätsbedingung erfüllen muss. Tupel dieser Art nennen wir zyklische Transversale. Ziel der vorliegenden Arbeit ist es daher, eine Grundlage zur weiteren Erforschung dieses verallgemeinernden Paradigmas der zyklischen Transversale zu schaffen. Davon ausgehend werden zuerst die zentralen Objekte dieser Arbeit, so genannte zyklische-Transversale- Polytope, definiert und analysiert. Diese Analyse führt einerseits zu einer Identifikation wesentlicher Meta-Parameter, die bei der Klassifikation dieser Polytope von Bedeutung sind, und andererseits zu einer Untersuchung kombinatorischer Eigenschaften der Polytope, die beispielsweise in einer Charakterisierung der Adjazenz ihrer Ecken mündet. Nach einem Beweis der anfänglichen Behauptung, dass Cut-Polytope und Stable- Set-Polytope neben anderen in der Literatur bekannten Polytopen zu den zyklische- Transversale-Polytopen gehören, erfolgt der Beweis einer notwendigen Bedingung für zyklische-Transversale-Polytope. Darauf aufbauend ergibt sich, dass nicht alle Kreuzpolytope zyklische-Transversale-Polytope sein können. Daran schließt sich eine Klassifikation der zyklische-Transversale-Polytope bis Dimension drei an. Durch Betrachtung in gewisser Weise allgemeinster zyklische-Transversale-Polytope wird außerdem ein Einblick in die Struktur gültiger Ungleichungen für zyklische-Transversale- Polytope gewährt. Dadurch kann eine Klasse gültiger Ungleichungen identifiziert werden, die die so genannten Odd-Set-Ungleichungen für Paritätspolytope verallgemeinert. Computergestützte Berechnungen zusätzlicher Ungleichungen und deren schematische Visualisierung ergänzen diese Betrachtung. Schließlich werden Relaxierungen von zyklische-Transversale-Polytopen und ihre Eigenschaften beschrieben. Die Konstruktion erweiterter Formulierungen von zyklische- Transversale-Polytopen vervollständigen die vorliegende Arbeit.

In the literature, classical combinatorial optimization problems such as the max-cut problem or the stable set problem, alternatively the associated cut and stable set polytopes, have been widely treated and discussed. This work provides a unified view of these two and other problems. The problems studied here can be described in terms of selected tuples of binary vectors whose sum must satisfy a parity condition. We call tuples of this type cyclic transversals. Thus, the aim of the present dissertation is to provide a basis for further research of this generalizing paradigm of cyclic transversals. Starting from this, the central objects of this work, so-called cyclic transversal polytopes, are first defined and analyzed. This analysis leads, on the one hand, to an identification of essential meta-parameters relevant in the classification of these polytopes, and, on the other hand, to an investigation of combinatorial properties of the polytopes, resulting, for example, in a characterization of the adjacency of their vertices. After a proof of the initial assertion that cut polytopes and stable set polytopes belong to the cyclic transversal polytopes among other polytopes known in the literature, a proof of a necessary condition for cyclic transversal polytopes is given. Based on this it follows that not all cross polytopes can be cyclic transversal polytopes. This is followed by a classification of cyclic transversal polytopes up to dimension three. By considering in some sense most general cyclic transversal polytopes, insight into the structure of valid inequalities for cyclic transversal polytopes is also provided. Thus, a class of valid inequalities can be identified which generalizes the so-called odd-set inequalities for parity polytopes. Computer-aided computations of additional inequalities and their schematic visualizations supplement this review. Finally, relaxations of cyclic transversal polytopes and their properties are described. The construction of extended formulations of cyclic transversal polytopes complete the present work.