Approximation algorithms for independent set problems on hypergraphs
Elena Losievskaja · Opin vísindi (Opin vísindi) · 2009
This thesis deals with approximation algorithms for the Maximum Indepen-dent Set and the Minimum Hitting Set problems on hypergraphs. As a hyper-graph is a generalization of a graph, the question is whether the best known approximations on graphs can be extended to hypergraphs. We consider greedy, local search and partitioning algorithms. We introduce a general technique, called shrinkage reduction, that reduces the worst case analysis of certain algorithms on hypergraphs to their analysis on ordinary graphs. This technique allows us to prove approximation ratios for greedy and local search algorithms for the Maximum Weak Independent Set problem on weighted and unweighted bounded-degree hypergraphs. For the weighted case we improve bounds using a simple partitioning algorithm. We also con-sider two variations of the max-greedy algorithms for the Maximum Strong Independent Set problem. We describe an SDP-based approach for the Maximum Weak Independent