Almost optimal set covers in finite VC-dimension |
| |
Authors: | H Brönnimann M T Goodrich |
| |
Institution: | (1) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA;(2) Department of Computer Science, Johns Hopkins University, 21218 Baltimore, MD, USA |
| |
Abstract: | We give a deterministic polynomial-time method for finding a set cover in a set system (X, ℛ) of dual VC-dimensiond such that the size of our cover is at most a factor ofO(d log(dc)) from the optimal size,c. For constant VC-dimensional set systems, which are common in computational geometry, our method gives anO(logc) approximation factor. This improves the previous Θ(log⋎X⋎) bound of the greedy method and challenges recent complexity-theoretic lower bounds for set covers (which do not make any
assumptions about the VC-dimension). We give several applications of our method to computational geometry, and we show that
in some cases, such as those arising in three-dimensional polytope approximation and two-dimensional disk covering, we can
quickly findO(c)-sized covers.
The first author was supported in part by NSF Grant CCR-90-02352 and Ecole Normale Supérieure. The second author's research
was supported by the NSF and DARPA under Grant CCR-8908092, and by the NSF under Grants IRI-9116843 and CCR-9300079. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|