Login
- Originaltitel:
- Circuits, Cutting Planes, and Compact Formulations
- Übersetzter Titel:
- Circuits, Schnittebenen und kompakte Formulierungen
- Autor:
- Brugger, Matthias
- Jahr:
- 2024
- Dokumenttyp:
- Dissertation
- Fakultät/School:
- TUM School of Computation, Information and Technology
- Betreuer:
- Schulz, Andreas S. (Prof. Dr.)
- Gutachter:
- Schulz, Andreas S. (Prof. Dr.); Kaibel, Volker (Prof. Dr.); Borgwardt, Steffen (Prof. Dr.)
- Sprache:
- en
- Fachgebiet:
- MAT Mathematik
- TU-Systematik:
- MAT 001
- Kurzfassung:
- We study three fundamental aspects of the theory of integer and linear programming. First, we study polyhedra whose integer hull is obtained by means of certain cutting planes and show that they are hard to recognize. Second, we explore the limitations of a technique for bounding sizes of extended formulations. Finally, we consider circuits and circuit diameters of polyhedra and investigate whether bounded counterexamples to the Hirsch conjecture may disprove its circuit analogue.
- Übersetzte Kurzfassung:
- Diese Arbeit widmet sich drei theoretischen Aspekten der ganzzahligen und linearen Optimierung. Zuerst untersuchen wir Polyeder, deren ganzzahlige Hülle sich mit bestimmten Schnittebenen erreichen lässt. Dann beschäftigen wir uns mit den Grenzen einer Technik, um Größen erweiterter Formulierungen zu beschränken. Schließlich betrachten wir Circuits und Circuit-Durchmesser von Polyedern und untersuchen Polytope, die die Hirsch-Vermutung widerlegen, im Circuit-Fall.
- WWW:
- https://mediatum.ub.tum.de/?id=1721226
- Eingereicht am:
- 26.09.2023
- Mündliche Prüfung:
- 13.03.2024
- Dateigröße:
- 1598779 bytes
- Seiten:
- 147
- Urn (Zitierfähige URL):
- https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20240313-1721226-1-3
- Letzte Änderung:
- 11.11.2024
BibTeX