One document found

Dissertation

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

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...