Analyse und exemplarische Implementation eines klassischen Approximationsalgorithmus für das NP-vollständige Problem Vertex Cover

Abstract

Das Ziel der vorliegenden Arbeit ist die Analyse und exemplarische Implementation des im Jahr 1981 von Reuven Bar-Yehuda und Shimon Even veröffentlichten Approximationsalgorithmus für das Problem Vertex Cover. Einleitend wird das gewichtete Vertex-Cover- Problem vorgestellt, das im Verlauf der Arbeit wiederholt aufgegriffen und schließlich als NP-vollständig nachgewiesen wird. Im ersten Teil der Arbeit werden grundlegenden Konzepte der NP-Vollständigkeit aufgearbeitet, formal definiert und mit Hilfe von Beispielen veranschaulicht. Zudem wird das für den Algorithmus benötigte Hintergrundwissen aus Bereichen der Approximationsalgorithmen und der linearen Programmierung erläutert. Die anschließende Analyse des Algorithmus erfolgt anhand einer ausführlichen Beschreibung des Ablaufs, einer exemplarischen Python-Implementierung inklusive Laufzeittests und einer detaillierten Ausarbeitung der Beweise. Abschließend wird die historische Bedeutung der Entwicklung der ersten Primal-Dual-Methode für einen Approximationsalgorithmus durch Bar-Yehuda und Even dargestellt. Das Verfahren wurde in der Programmiersprache Python implementiert, und die lineare Zeitkomplexität konnte mit einer Laufzeitanalyse bestätigt werden. Die Analyse ergab zudem, dass eine Python-Implementation des Verfahrens besondere Schritte erfordert, um das vorgegebene lineare Laufzeitverhalten zu gewährleisten. Eine schrittweise Erklärung konnte die Beweise übersichtlich wiedergeben und die Primal-Dual-Approximations-Methode hervorheben. Diese wurde von Bar-Yehuda und Even zum ersten Mal für die iterative Konstruktion einer approximierten Lösung eines NP-vollständigen Problems verwendet und ermöglichte seitdem den Entwurf von vielen weiteren Approximationsalgorithmen für NP-vollständige Probleme.

The goal of this thesis is to analyse and implement the approximation algorithm for the vertex cover problem introduced in 1981 by Reuven Bar-Yehuda and Shimon Even. The thesis begins with an introduction to the weighted vertex cover problem, which will play a recurring role in later chapters and will be demonstrated to be NP-complete. In chapter 2, the fundamental concepts of NP-completeness will be established and explained in detail, accompanied by multiple illustrative examples. Additional concepts from approximation algorithms and linear programming, essential for the algorithm, will be presented in this chapter. The subsequent study of the algorithm is broken down into three parts: Firstly, the algorithm process will be explained step by step. Secondly, an exemplary Python implementation including runtime tests will be given. Lastly, the underlying proof of the algorithm will be elaborated in detail. The last chapter will conclude by presenting the historical significance of the development of the first primal-dual method for an approximation algorithm by Bar-Yehuda and Even. The algorithm was implemented in Python and shown to achieve linear runtime, verified through multiple runtime tests. The study further revealed that ensuring linear runtime in a Python implementation of the method requires special steps to be taken. A systematic explanation provided the necessary proof in a clear and illustrative manner and highlighted the use of the primal-dual approximation method. Originally developed by Bar-Yehuda and Even for the iterative construction of approximate solutions to NP-complete problems, this method has since enabled the design of numerous other approximation algorithms for such problems.