PT Unknown
AU El Ouali, M
TI Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms
PY 2013
PU Christian-Albrechts-Universität zu Kiel
WP https://macau.uni-kiel.de/receive/diss_mods_00013153
LA en
DE Approximation Algorithms; Hypergraphs; Complexity; Inapproximability; Optimization Problems; ComplexitApproximationsalgorithmen; Hypergraphen; Komplexität; Nicht-Approximierbarkeit; Optimierungsprobleme
AB 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.
PI Kiel
ER