User: Guest  Login
If you experience problems opening the document, please try this link.
Original title:
Homologous Circulations, Voronoi Cells, and Densest Subgraphs
Translated title:
Homologe Zirkulationen, Voronoi-Zellen und dichteste Teilgraphen
Author:
Seidel, Ina
Year:
2023
Document type:
Dissertation
Faculty/School:
TUM School of Computation, Information and Technology
Advisor:
Weltge, Stefan (Prof. Dr.)
Referee:
Weltge, Stefan (Prof. Dr.); Walter, Matthias (Prof. Dr.)
Language:
en
Subject group:
MAT Mathematik
Keywords:
polyhedra, surface-embedded graphs, homology, circulations, lattices, Voronoi cells, extension complexity, densest subgraph problem
TUM classification:
MAT 500; MAT 910
Abstract:
This thesis considers three different topics in discrete optimization from a polyhedral perspective. The first chapter deals with finding a minimum-cost, non-negative, integer circulation in a surface-embedded digraph that is homologous to a given circulation. In the second chapter, we provide lower and upper bounds on the extension complexities of Voronoi cells of lattices. The third chapter is concerned with different aspects of the densest subgraph problem.
Translated abstract:
Diese Arbeit betrachtet drei Themen der diskreten Optimierung aus polyedrischer Sicht. Das erste Kapitel befasst sich mit der Suche nach einer minimalen, nicht-negativen, ganzzahligen Zirkulation in einem eingebetteten Digraphen, die in einer gegebenen Homologieklasse liegt. Im zweiten Kapitel geben wir untere und obere Schranken für die Größe erweiterter Formulierungen von Voronoi-Zellen von Gittern an. Das dritte Kapitel befasst sich mit verschiedenen Aspekten dichtester Teilgraphen.
WWW:
https://mediatum.ub.tum.de/?id=1692898
Date of submission:
11.01.2023
Oral examination:
20.04.2023
File size:
887454 bytes
Pages:
100
Urn (citeable URL):
https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20230420-1692898-1-2
Last change:
15.05.2023
 BibTeX