Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-11781
For citation please use:
Main Title: Tropical bisectors and diameters of simplicial complexes
Translated Title: Tropische Bisektoren und Diameter von Simplizialkomplexen
Author(s): Criado Gallart, Francisco
Advisor(s): Joswig, Michael
Santos Leal, Francisco
Referee(s): Joswig, Michael
Rote, Günter
Santos Leal, Francisco
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Has Part: 10.14279/depositonce-11546
Language Code: en
Abstract: Tropical geometry is a discrete analogue of algebraic geometry where addition is replaced by taking the minimum (or maximum) and multiplication is replaced by addition. It is an active research eld where tropical analogues of geometric concepts, like linear spaces, varieties, polytopes or volume, are in different stages of development. The interest of these analogues is twofold: their combinatorial nature helps us understand difficult geometric objects and develop algorithms for them, and at the same time they bring geometric language to the field of mathematical optimization. The application of tropical geometry to linear programming has been introduced in [5], where tropical ideas were used to prove that log-barrier interior point linear programming algorithms, known to run in weakly polynomial time, cannot run in strongly polynomial time. In a similar spirit, we are interested in the study of the tropical distance and in particular how it relates to existing tropical linear programming algorithms. The problem of algorithmically solving tropical linear programs is particularly interesting because it lies in the classes of NP and co-NP problems, but no polynomial time algorithm for it is known yet. The problem has an interpretation in the context of metric tropical geometry, but it is still unknown how to use this geometric information for tropical linear feasibility algorihtms. For this reason we introduce here the study of tropical bisectors and Voronoi diagrams, as well as algorithms for their computation.Even though our study focuses on these objects on their own, they will be necessary for understanding tropical analogues for the ellipsoid method or the Kaczmarz iteration algorithm. It is relevant to develop such analogues, because both of these algorithms run in (weakly) polynomial time for classical linear programming. The rest of the thesis looks at the diameter of simplicial complexes, a combinatorial generalization of polytopes. Both classical and tropical simplex methods for linear programming involve exploring the dual graph of some simplicial sphere. Thus, studying the diameter of such complexes is relevant for the understanding of the simplex method's computational complexity. We present new constructions for abstract simplicial complexes with asymptotically large diameter, close to the theoretical upper bound, using a probabilistic construction. We also construct small simplicial spheres with large diameter using a computational heuristic approach, and we develop the topological analogue of the prismatoids used by Santos to disprove the Hirsch conjecture.
Tropische Geometrie ist ein diskretes Analogon zu algebraischer Geometrie, bei dem Addition durch Minimumsbildung (oder Maximumsbildung) und Multiplikation durch Addition ersetzt wird. Sie ist ein aktives Forschungsfeld; tropische Analoga zu geometrischen Konzepten wie Volumina, Polytopen, linearen Räumen oder Varietäten sind in unterschiedlichen Stadien der Entwicklung. Diese Analoga sind in zweierlei Hinsicht interessant: Zum einen hilft uns ihre kombinatorische Natur, komplizierte geometrische Objekte zu verstehen und Algorithmen für sie zu entwickeln. Zum anderen ermöglichen sie die Verwendung geometrischer Sprache für mathematische Optimierung. Anwendungen tropischer Geometrie auf lineare Programmierung wurden erstmals in [5] untersucht. Dort werden tropische Ideen verwendet, um zu beweisen, dass Innere-Punkte-Methoden mit logarithmischer Barrier-Funktion, die bekanntermaÿen in schwach polynomineller Zeit terminieren, nicht in stark polynomineller Zeit terminieren können. Diesem Ansatz folgend untersuchen wir hier die tropische Abstandsfunktion auch im Zusammenhang mit bestehenden Algorithmen zur tropischen linearen Programmierung. Das Problem der algorithmischen Lösung tropischer linearer Programme ist besonders interessant, da es im Schnitt der Klassen NP und Co-NP liegt, aber noch kein Lösungsalgorithmus mit polynomineller Laufzeit bekannt ist. Es lässt sich im Kontext metrischer tropischer Geometrie interpretieren; bisher ist allerdings unklar, wie sich diese geometrische Information in Algorithmen zur Bestimmung der Lösbarkeit tropischer linearer Programme einbinden lässt. Aus diesem Grund stellen wir hier eine Untersuchung von tropischen Voronoi-Diagrammen, tropischen Bisektoren und Algorithmen zu ihrer Berechnung vor. Unsere Arbeit legt den Fokus auf die Untersuchung dieser Objekte an sich; sie werden aber auch für das Verständnis tropischer Analoga zur Ellipsoidmethode oder zur Kaczmarz-Methode notwendig sein. Die Entwicklung solcher Analoga ist relevant, da beide Algorithmen für klassische lineare Programme (schwach) polynominelle Laufzeit aufweisen. Der Rest der Arbeit befasst sich mit dem Durchmesser von Simplizialkomplexen, einer kombinatorischen Verallgemeinerung von Polytopen. Sowohl klassische als auch tropische Simplex-Methoden für lineare Programmierung beinhalten die Untersuchung des dualen Graphen einer simplizialen Sphäre. Die Untersuchung des Durchmessers solcher Komplexe ist daher für das Verständnis der Komplexität dieser Methoden relevant. Wir präsentieren neue Konstruktionen abstrakter Simplizialkomplexe mit asymptotisch groÿem Durchmesser nahe an der theoretischen oberen Schranke, unter Verwendung einer probabilistischen Konstruktion. Wir konstruieren weiterhin, mithilfe eines heuristischen Ansatzes, kleine simpliziale Sphären mit groÿem Durchmesser, und entwickeln das topologische Analogon zu den Prismatoiden, die Santos verwendet um die Hirsch-Vermutung zu widerlegen.
URI: https://depositonce.tu-berlin.de/handle/11303/12986
http://dx.doi.org/10.14279/depositonce-11781
Exam Date: 30-Nov-2020
Issue Date: 2021
Date Available: 23-Apr-2021
DDC Class: 516 Geometrie
Subject(s): computational geometry
Hirsch conjecture
discrete geometry
tropical geometry
algorithmische Geometrie
Hirsch-Vermutung
diskrete Geometrie
tropische Geometrie
License: http://rightsstatements.org/vocab/InC/1.0/
Appears in Collections:FG Diskrete Mathematik / Geometrie » Publications

Files in This Item:
criado_gallart_francisco.pdf
Format: Adobe PDF | Size: 1.12 MB
DownloadShow Preview
Thumbnail

Item Export Bar

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