| Hardness of set cover with intersection 1 (2000) | |||||||||||||
Abstract | |||||||||||||
| We consider a restricted version of the general Set Covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the Set Covering problem with intersection 1 cannot be approximated within a o(logn) factor in random polynomial time unless NP subset of or equal to ZTIME(n(O(loglogn))). We also observe that the main challenge in derandomizing this reduction lies in finding a hitting set for large volume combinatorial rectangles satisfying certain intersection properties. These properties are not satisfied by current methods of hitting set construction. An example of a Set Covering problem with the intersection 1 property is the problem of covering a given set of points in two or higher dimensions using straight lines; any two straight lines intersect in at most one point. The best approximation algorithm currently known for this problem has an approximation factor of theta(log n), and beating this bound seems hard. We observe that this problem is Max-SNP-Hard. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||