Combinatorial Algorithms for Covering and Scheduling Problems

Leichter, Marilena Susan

Marilena Susan Leichter

If you experience problems opening the document, please try this link.

Original title:: Combinatorial Algorithms for Covering and Scheduling Problems
Translated title:: Kombinatorische Algorithmen für Covering- und Schedulingprobleme
Author:: Leichter, Marilena Susan
Year:: 2021
Document type:: Dissertation
Faculty/School:: Fakultät für Mathematik
Advisor:: Schulz, Andreas S. (Prof. Dr.)
Referee:: Schulz, Andreas S. (Prof. Dr.); Moseley, Benjamin (Prof.); Peis, Britta (Prof. Dr.)
Language:: en
Subject group:: MAT Mathematik
TUM classification:: MAT 600
Abstract:: We study combinatorial optimization problems related to covering and scheduling problems, such as the Minimum Hitting Set of Bundles problem, the Generalized Min Sum Set Cover problem, problems related to Matroid Intersection Covers, and the Bipartite Flow Scheduling problem. We present combinatorial approximation algorithms, study the computational complexity, and present polynomial-time algorithms for certain classes of instances.
Translated abstract:: Wir untersuchen kombinatorische Optimierungsprobleme, die mit Covering- und Schedulingproblemen zusammenhängen, wie z. B. das Minimum Hitting Set of Bundles Problem, das Generalized Min Sum Set Cover Problem, Probleme im Zusammenhang mit Matroid Intersection Covers und das Bipartite Flow Scheduling Problem. Wir stellen kombinatorische Approximationsalgorithmen vor, untersuchen die Komplexität und präsentieren polynomielle Algorithmen für bestimmte Klassen von Instanzen.
WWW:: https://mediatum.ub.tum.de/?id=1602044
Date of submission:: 30.03.2021
Oral examination:: 24.06.2021
File size:: 2715549 bytes
Pages:: 140
Urn (citeable URL):: https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20210624-1602044-1-9
Last change:: 06.09.2021
BibTeX