Internally funded project
Acronym: AlKoP
Start date : 13.03.2017
Website: https://www.cs12.tf.fau.de/forschung/projekte/alkop/
It is presumed that problems that are shown NP-complete cannot be solved in polynomial time. Nevertheles, solutions to these problems must be found, even if they are not optimal, as long as they can be generated quickly. Besides devising such fast approximation algorithms for combinatorial optimization problems, a considerable art is to determine the quality of the obtained solution in terms of the optimum solution without knowing it. Another important aspect of an approximation algorithm is to present a bad input, a so-called witness, that is an input where the algorithm may output quite a bad feasible solution that is far away from the optimum solution. Especially in the field of the Traveling Salesperson Problem there are some heuristics in use where the gap between witnesses and performance guarantees are still considerably large. In this focus of research, we would like to design good witnesses against some of these heuristics.
Man vermutet, dass NP-vollständige Probleme nicht in Polynomzeit gelöst werden können. Trotzdem müssen für Eingaben solcher Probleme zulässige Lösungen – oft unter Verzicht auf Optimalität, aber möglichst gut – berechnet werden, solange sie nur schnell erhalten werden. Beim Entwurf schneller und guter derartiger Algorithmen für kombinatorische Optimierungsprobleme setzt man häufig auf randomisierte und aus Approximationsalgorithmen. Bei letzteren ist es oft eine ganz große Herausforderung, die Qualität der erzielten Lösung in Beziehung zur optimalen Lösung, deren Wert ja unbekannt ist, zu setzen.
Ein weiterer wichtiger Aspekt eines Approximationsalgorithmus ist der, für diesen Algorithmus Eingaben anzugeben, sog. Zeugen, bei denen er Ausgaben erzeugt, die sehr weit weg von optimalen Lösung sind. Insbesondere im Gebiet der Approximationsalgorithmen für das sog. Rundreiseproblem gibt es eine Reihe von Heuristiken, bei denen die Lücken zwischen Leistungsgarantien und Zeugen sehr groß sind. In diesem Forschungsbereich wollen wir gute Zeugen gegen einiger dieser Heuristiken entwerfen.
Im Bereich der randomisierten Verfahren untersuchen wir sog. Random-Walk-basierte Algorithmen für das NP-vollständige Erfüllbarkeitsproblem.