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

68W25 Approximation algorithms
68P05 Data structures
Full Text: DOI