Reasoning about RoboCup soccer narratives
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
In the hitting set problem one is given m subsets of a finite set N and one has to find an X ⊂ N of minimum cardinality that "hits" (intersects) all of them. The problem is NP-hard. It is not known whether there exists a polynomial-time approximation algorithm for the hitting set problem with a finite performance ratio. Special cases of the hitting set problem are described for which finite performance ratios are guaranteed. These problems arise in a geometric setting. We consider special cases of the following problem: Given n compact subsets of Rd, find a set of straight lines of minimum cardinality so that each of the given subsets is hit by at least one line. The algorithms are based on several techniques of representing objects by points, not necessarily points on the objects, and solving (in some cases, only approximately) the problem of hitting the representative points. Finite performance ratios are obtained when the dimension, the number of types of sets to be hit and the number of directions of the hitting lines are bounded. © 1991.
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics
Ligang Lu, Jack L. Kouloheris
IS&T/SPIE Electronic Imaging 2002