Please use this identifier to cite or link to this item:
http://dx.doi.org/10.25673/110908
Title: | Cyclic transversal polytopes |
Author(s): | Frede, Jonas |
Referee(s): | Kaibel, Volker |
Granting Institution: | Otto-von-Guericke-Universität Magdeburg, Fakultät für Mathematik |
Issue Date: | 2023 |
Extent: | I, 138 Seiten |
Type: | Hochschulschrift |
Type: | PhDThesis |
Exam Date: | 2023 |
Language: | English |
URN: | urn:nbn:de:gbv:ma9:1-1981185920-1128635 |
Subjects: | Kombinatorik Graphentheorie Angewandte Mathematik 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. |
URI: | https://opendata.uni-halle.de//handle/1981185920/112863 http://dx.doi.org/10.25673/110908 |
Open Access: | Open access publication |
License: | (CC BY-SA 4.0) Creative Commons Attribution ShareAlike 4.0 |
Appears in Collections: | Fakultät für Mathematik |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Frede_Jonas_Dissertation_2023.pdf | Dissertation | 685.07 kB | Adobe PDF | View/Open |