Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-6433
Main Title: Combinatorics of tropical linear programming
Translated Title: Kombinatorik tropischer linearer Programmierung
Author(s): Loho, Georg
Advisor(s): Joswig, Michael
Referee(s): Joswig, Michael
Gaubert, Stéphane
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: The main topic of this work is the study of systems of inequalities where only the operations 'min' and '+' are used and which we call tropical linear inequality systems. An important algorithmic problem is to determine a point which fulfills all the inequalities. This problem, referred as the tropical feasibility problem, occurs in connection with scheduling as well as mean payoff games. It is analogous with the classical feasibility problem for linear inequality systems. We study these systems by means of sets of bipartite graphs. Methods from combinatorial optimization yield a characterization of these bipartite graphs, referred as covector graphs, in terms of minimal matchings. We start with a thorough investigation of polyhedra, which are naturally associated to shortest paths in weighted directed graphs. It leads to new covector decompositions of the tropical projective space. We reveal the connection with order polytopes and the boundary of the tropical projective space. Furthermore, we resolve a conjecture of Develin and Yu (2007). A second approach to examine tropical linear inequality systems arises by representing them as images of linear inequality systems over Puiseux series under a valuation map. We introduce the subfield of Puiseux fractions which is suitable for computations on a computer in contrast to Puiseux series, and we relate linear inequality systems over Puiseux fractions with linear inequality systems over the real numbers. Combining these ideas from classical halfspace arrangements with the covector decompositions leads to an abstraction in terms of signed tropical matroids which are an analogue of classical oriented matroids. This allows us to study tropical linear inequality systems with tools for polyhedral subdivisions. While tropical linear inequality systems correspond to regular subdivisions of subpolytopes of the product of two simplices, our arguments readily apply to not necessarily regular subdivisions as well. We design an algorithm to determine the feasibility of a tropical linear inequality system which also works for the generalized structure derived from not necessarily regular subdivisions. For regular subdivisions, the complexity is bounded by the entries of a minimal integer vector in a cone of the secondary fan of the product of two simplices.
Der Schwerpunkt dieser Arbeit liegt auf der Untersuchung von Ungleichungssystemen, in denen nur die Operationen "min" und "+" vorkommen und die wir tropische, lineare Ungleichungssysteme nennen. Ein wichtiges algorithmisches Problem besteht darin, einen Vektor zu finden, der alle Ungleichungen erfüllt. Dieses Problem tritt in Verbindung mit Scheduling sowie Mean-Payoff-Spielen auf, und es ist ein Analogon zum klassischen Zulässigkeitsproblem für lineare Ungleichungssysteme. Wir untersuchen diese Systeme mittels Mengen bipartiter Graphen. Methoden aus der kombinatorischen Optimierung liefern eine Charakterisierung dieser bipariten Graphen, die wir Kovektor-Graphen nennen, mittels minimaler Matchings. Wir beginnen mit einer gründlichen Untersuchung von Polyedern, die auf natürliche Weise mit kürzesten Wegen in einem Graph assoziiert werden können. Das führt zu neuen Kovektorzerlegungen des tropischen projektiven Raums. Wir zeigen die Verbindung zwischen Ordnungs-Polytopen und dem Rand des tropischen projektiven Raums auf. Ferner lösen wir eine Vermutung von Develin und Yu (2007). Ein weiterer Ansatz zur Analyse von tropischen linearen Ungleichungssystemen entsteht durch ihre Darstellung als Bilder linearer Ungleichungssysteme über Puiseux-Reihen unter einer Bewertungsabbildung. Wir führen den Teilkörper der Puiseux-Brüche ein, welcher im Gegensatz zu Puiseux-Reihen geeignet ist für Berechnungen am Computer, und wir stellen eine Verbindung zwischen linearen Ungleichungssystemen über dem Körper der Puiseux-Brüche mit linearen Ungleichungssystemen über den reellen Zahlen her. Verbindet man die Ideen zu klassischen Halbraum-Konfigurationen mit den Kovektor-Zerlegungen, so führt dies zu einer Abstraktion, welche durch vorzeichenbehaftete tropische Matroide ausgedrückt wird, die wiederum ein Analogon zu klassischen orientierten Matroiden darstellen. Dies ermöglicht es uns tropische lineare Ungleichungssysteme mit Mitteln polyedrischer Unterteilungen zu studieren. Während tropische lineare Ungleichungssysteme in Korrespondenz mit regulären Unterteilungen von einem Produkt zweier Simplizes stehen, lassen sich unsere Argumente direkt auch auf nicht-notwendigerweise reguläre Unterteilungen übertragen. Wir konzipieren einen Algorithmus, der die Zulässigkeit eines tropischen linearen Ungleichungssystems bestimmt und auch für die verallgemeinerte Struktur funktioniert, die wir anhand nicht-notwendigerweise regulärer Unterteilungen definiert haben. Für reguläre Unterteilungen ist die Komplexität durch die Einträge eines minimalen ganzzahligen Vektors in einem Kegel des Sekundärfächers des Produkts zweier Simplizes beschränkt.
URI: https://depositonce.tu-berlin.de//handle/11303/7158
http://dx.doi.org/10.14279/depositonce-6433
Exam Date: 5-Sep-2017
Issue Date: 2017
Date Available: 22-Nov-2017
DDC Class: DDC::500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
Subject(s): linear programming
tropical convexity
polyhedral subdivision
signed tropical matroid
matching
lineare Programmierung
tropische Konvexität
polyedrische Unterteilung
tropischer Matroid mit Vorzeichen
Usage rights: Terms of German Copyright Law
Appears in Collections:Fachgebiet Diskrete Mathematik / Geometrie » Publications

Files in This Item:
File Description SizeFormat 
loho_georg.pdf3.52 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.