Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331970 | Information Processing Letters | 2005 | 5 Pages |
Abstract
We present an approximation algorithm for the hitting set problem when the VC-dimension of the set system is small. Our algorithm uses a linear programming relaxation to compute a probability measure for which É-nets are always hitting sets (see Corollary 15.6 in Pach and Agarwal [Combinatorial Geometry, J. Wiley, New York, 1995]). The comparable algorithm of Brönnimann and Goodrich [Almost optimal set covers in finite VC-dimension, Discrete Comput. Geom. 14 (1995) 463] computes such a probability measure by an iterative reweighting technique. The running time of our algorithm is comparable with theirs, and the approximation ratio is smaller by a constant factor. We also show how our algorithm can be parallelized and extended to the minimum cost hitting set problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Guy Even, Dror Rawitz, Shimon (Moni) Shahar,