# zbMATH — the first resource for mathematics

Parameterized approximation algorithms for hitting set. (English) Zbl 1242.68368
Solis-Oba, Roberto (ed.) et al., Approximation and online algorithms. 9th international workshop, WAOA 2011, Saarbrücken, Germany, September 8–9, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-29115-9/pbk). Lecture Notes in Computer Science 7164, 63-76 (2012).
Summary: We are going to analyze simple search tree algorithms for approximating $$d$$-Hitting Set, focussing on the case of factor-2 approximations for $$d = 3$$. We also derive several results for hypergraph instances of bounded degree, including a new polynomial-time approximation.
For the entire collection see [Zbl 1241.68041].

##### MSC:
 68W25 Approximation algorithms 68P05 Data structures
Full Text: