Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms

Diese Arbeit befasst sich mit dem Entwurf und der mathematischen Analyse von randomisierten Approximationsalgorithmen für das Hitting Set Problem und das b-Matching Problem in Hypergraphen. Zuerst präsentieren wir einen randomisierten Algorithmus für das Hitting Set Problem, der auf linearer Programmierung basiert. Mit diesem Verfahren und einer Analyse, die auf der probabilistischen Methode fußt, erreichen wir für verschiedene Klassen von Instanzen drei neue Approximationsgüten, die die bisher bekannten Ergebnisse (Krevilevich [1997], Halperin [2001]) für das Problem verbessern. Die Analysen beruhen auf Konzentrationsungleichungen für Summen von unabhängigen Zufallsvariablen aber auch Martingal-basierten Ungleichungen, wie die aus der Azuma-Ungleichung abgeleitete Bounded Difference-Inequality, in Kombination mit kombinatorischen Argumenten. Für das b-Matching Problem in Hypergraphen analysieren wir zunächst seine Komplexität und erhalten zwei neue Ergebnisse. Wir geben eine polynomielle Reduktion von einer Instanz eines geeigneten Problems zu einer Instanz des b-Matching-Problems an und zeigen ein Nicht-Approximierbarkeitsresultat für das Problem in uniformen Hypergraphen. Dieses Resultat verallgemeinert das Ergebnis von Safra et al. (2006) von b = 1 auf b in O(l/log(l))). Safra et al. zeigten, dass es für das 1-Matching Problem in uniformen Hypergraphen unter der Annahme P != NP keinen polynomiellen Approximationsalgorithmus mit einer Ratio O(l/log(l)) gibt. Weiterhin beweisen wir, dass es in uniformen Hypergraphen mit beschränktem Knoten-Grad kein PTAS für das Problem gibt, es sei denn P = NP.