000K  utf8
1100  $c2013
1500  eng
2050  urn:nbn:de:gbv:8-diss-131534
3000  El Ouali, Mourad
4000  Randomisierte Approximation für das Matching- und Knotenüberdeckung Problem in Hypergraphen: Komplexität und Algorithmen$hChristian-Albrechts-Universität zu Kiel  [El Ouali, Mourad]
4000  Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms$hChristian-Albrechts-Universität zu Kiel  [El Ouali, Mourad]
4030  Kiel$nChristian-Albrechts-Universität zu Kiel
4209  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.
4209  This thesis studies the design and mathematical analysis of randomized approximation algorithms for the hitting set and b-matching problems in hypergraphs. We present a randomized algorithm for the hitting set problem based on linear programming. The analysis of the randomized algorithm rests upon the probabilistic method, more precisely on some concentration inequalities for the sum of independent random variables plus some martingale based inequalities, as the bounded difference inequality, which is a derived from Azuma inequality. In combination with combinatorial arguments we achieve some new results for different instance classes that improve upon the known approximation results for the problem (Krevilevich (1997), Halperin (2001)). We analyze the complexity of the b-matching problem in hypergraphs and obtain two new results. We give a polynomial time reduction from an instance of a suitable problem to an instance of the b-matching problem and prove a non-approximability ratio for the problem in l-uniform hypergraphs. This generalizes the result of Safra et al. (2006) from b=1 to b in O(l/log(l)). Safra et al. showed that the 1-matching problem in l-uniform hypergraphs can not be approximated in polynomial time within a ratio O(l/log(l)), unless P = NP. Moreover, we show that the b-matching problem on l-uniform hypergraphs with bounded vertex degree has no polynomial time approximation scheme PTAS, unless P=NP.
4950  https://nbn-resolving.org/urn:nbn:de:gbv:8-diss-131534$xR$3Volltext$534
4961  https://macau.uni-kiel.de/receive/diss_mods_00013153
5051  510
5550  Approximation Algorithms
5550  Approximation Algorithms
5550  ComplexitApproximationsalgorithmen
5550  Complexity
5550  Hypergraphen
5550  Hypergraphs
5550  Hypergraphs
5550  Inapproximability
5550  Komplexität
5550  Nicht-Approximierbarkeit
5550  Optimierungsprobleme
5550  Optimization Problems