Abstract We present an approximation algorithm for the hitting set problem when the VC-dimension of the set system is small. Our algorithm builds on Pach & Agarwal [7], and we show how it can be parallelized and extended to the minimum,cost hitting set problem. The running time of the proposed algorithm is comparable with that of Br onnimann & Goodrich [2], and the approximation ratio is smaller by a constant factor.