Combinatorics of tropical linear programming
| dc.contributor.advisor | Joswig, Michael | |
| dc.contributor.author | Loho, Georg | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Joswig, Michael | |
| dc.contributor.referee | Gaubert, Stéphane | |
| dc.date.accepted | 2017-09-05 | |
| dc.date.accessioned | 2017-11-22T16:43:29Z | |
| dc.date.available | 2017-11-22T16:43:29Z | |
| dc.date.issued | 2017 | |
| dc.description.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. | en |
| dc.description.abstract | 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. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/7158 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-6433 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | de |
| dc.subject.other | linear programming | en |
| dc.subject.other | tropical convexity | en |
| dc.subject.other | polyhedral subdivision | en |
| dc.subject.other | signed tropical matroid | en |
| dc.subject.other | matching | en |
| dc.subject.other | lineare Programmierung | de |
| dc.subject.other | tropische Konvexität | de |
| dc.subject.other | polyedrische Unterteilung | de |
| dc.subject.other | tropischer Matroid mit Vorzeichen | de |
| dc.title | Combinatorics of tropical linear programming | en |
| dc.title.translated | Kombinatorik tropischer linearer Programmierung | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | domain | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Diskrete Mathematik / Geometrie | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.group | FG Diskrete Mathematik / Geometrie | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |