ISBN 9783843949392

978-3-8439-4939-2, Reihe Mathematik

Eva M. Schmidt
Robust Multicovers: Algorithms and Complexity

239 Seiten, Dissertation Technische Universität Kaiserslautern (2021), Softcover, A5

Zusammenfassung / Abstract

Das große Interesse an robusten Überdeckungsproblemen ist vielfältig, besonders durch die Vielzahl realer Anwendungsmöglichkeiten und die zusätzliche Betrachtung von Unsicherheiten, die vielen praktischen Problemen innewohnen.

In dieser Arbeit stellen wir ein neues robustes Überdeckungsproblem vor, das wir Robust Min q-Multiset-Multicover nennen, wobei q eine fixe natürliche positive Zahl darstellt. Dieses und weitere verwandte Probleme werden sorgfältig ausgearbeitet. Die gemeinsame Idee dieser Probleme ist es, bei gegebener Auswahl an Teilmengen einer Grundmenge, die Auswahlhäufigkeit jeder Teilmenge so zu bestimmen, dass die unsichere Nachfrage aller vorkommenden Elemente erfüllt ist. Im Unterschied zu allgemeinen Überdeckungsproblemen darf hier jede Teilmenge höchstens q ihrer Elemente überdecken. Durch Variation der Eigenschaften der vorkommenden Elemente entstehen so vier interessante robuste Überdeckungsprobleme, die untersucht werden.

Wir analysieren ausführlich die Komplexität dieser Probleme. Dabei betrachten wir auch Einschränkungen in spezielle Klassen von Unsicherheitsmengen. Für ein gegebenes Problem geben wir entweder einen Polynomialzeit-Algorithmus an oder zeigen, dass es, solange nicht P = NP gilt, einen solchen Algorithmus nicht geben kann. Weiterhin beweisen wir für den Großteil der Fälle sogar, dass aller Voraussicht nach auch ein polynomielles Approximationsschema für die schweren Varianten nicht möglich ist.

Außerdem streben wir nach Approximationen und Approximationsalgorithmen für diese schweren Varianten. Hier fokussieren wir uns auf Robust Min q-Multiset-Multicover. Für eine umfangreiche Klasse von Unsicherheitsmengen präsentieren wir den ersten Polynomialzeit-Approximationsalgorithmus für Robust Min q-Multiset-Multicover mit beweisbarer Güte.