Academic
Publications
Hitting sets when the VC-dimension is small

Hitting sets when the VC-dimension is small,10.1016/j.ipl.2005.03.010,Information Processing Letters,Guy Even,Dror Rawitz

Hitting sets when the VC-dimension is small   (Citations: 33)
BibTex | RIS | RefWorks Download
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.
Journal: Information Processing Letters - IPL , vol. 95, no. 2, pp. 358-362, 2005
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...One version of their approaches is indeed based on LP relaxation [Lon01, ERS05]...
    • ...Let Opt0 be the value of this LP. Known analysis [Lon01, ERS05] implies that the integrality...

    Timothy M. Chanet al. Approximation Algorithms for Maximum Independent Set of Pseudo-Disks

    • ...Our algorithms rely on the fact that, for sets systems with finite VC-dimension d, there are algorithms which can compute a set-cover of the set system whose size is at most O(d� log OP T � OP T ) where OP T is the size of the minimum set-cover [16], [17]...
    • ...Since there is a set-cover of (X, R′) of size at most |OP T |, one can find a cover of size O(OP T log OP T ) in polynomial time using [16], [17]...

    Onur Tekdaset al. Sensor Placement for Triangulation-Based Localization

    • ...A shorter, simpler pro of was given by Even et al. [5]...

    Nabil H. Mustafaet al. Improved Results on Geometric Hitting Set Problems

    • ...The question is, what is a good upper bound on the size of an L n -net over all families of n disks and all 1 ≤ L ≤ n? Clearly this bound must be at least n L and we want to know how much larger it must be. We know [7, 16] that if for any type of object (disks, triangles, axes-parallel rectangles) there are L n -nets of size at most n...
    • ...Clearly, this bound on the weight is at least as large as W L , where W is the total weight of all the objects, and can be shown to be O( W L logn) for fairly general geometric objects [16]...
    • ...As we have remarked in Section 1, the fact that an algorithm for constructing nets can be used for rounding is well known [7, 23, 16]...

    Kasturi Varadarajan. Weighted geometric set cover via quasi-uniform sampling

    • ...Besides being interesting in its own right, this question has an algorithmic motivation, since as shown in [7] and [13] the existence of smaller nets supplies improved approximation algorithms for the set cover problem and the hitting set problem in the corresponding geometric scenarios...

    Noga Alon. A Non-linear Lower Bound for Planar Epsilon-Nets

Sort by: