Almost optimal set covers in finite VC-dimension: (preliminary version)

ABSTRACT

We give a deterministic polynomial time method for finding a set cover in a set system (X,R) of VC-dimension d such that the size of our cover is at most a factor of O(dlog(dc)) from the optimal size, c. For constant VC-dimension set systems, which are common in computational geometry, our method gives an O(logc) approximation factor. This improves the previous &THgr;(log |X|) bound of the greedy method and beats recent complexity-theoretic lower bounds for set covers (which don't make any assumptions about VC-dimension). We give several applications of our method to computational geometry, and we show that in some cases, such as those that arise in 3-d polytope approximation and 2-d disc covering, we can quickly find O(c)-sized covers.

REFERENCES

• 1: Esther M. Arkin , Henk Meijer , Joseph S. B. Mitchell , David Rappaport , Steven S. Skiena, Decision trees for geometric models, Proceedings of the ninth annual symposium on Computational geometry, p.369-378, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161167]
• 2: P. Assouad. Densit~ et dimension. Ann. Institut Fourier, Grenoble, 3:232-282, 1983.
• 3: E. B. Baum, On learning a union of half spaces, Journal of Complexity, v.6 n.1, p.67-101, Mar. 1990 [doi>10.1016/0885-064X(90)90012-3]
• 4: M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
• 5: Bonnie Berger , John Rompel , Peter W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.454-477, December 1994, Research Triangle Park, North Carolina, United States
• 6: Avrim Blum , Ronald L. Rivest, Training a 3-node neural network is NP-complete, Proceedings of the first annual workshop on Computational learning theory, p.9-18, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 7: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 8: H. BrSnnimann. An implementation of MIN HITTING SET heuristics. Manuscript, 1994.
• 9: Herv~ BrSnnimann, Bernard Chazelle, and Jill Matou~ek. Product range spaces, sensitive sampling, and derandomization. In Proc. 3dth Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 93), pages 400-409, 1993.
• 10: Bernard Chazelle, An optimal convex hull algorithm and new results on cuttings (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.29-38, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185345]
• 11: Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
• 12: Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , Micha Sharir , Emo Welzl, Improved bounds on weak &egr;-nets for convex sets, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.495-504, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167222]
• 13: B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Uombmator~ca, 10(3):229-249, 1990.
• 14: Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
• 15: B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
• 16: V. Chvatal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4:233-235, 1979.
• 17: K. L. Clarkson. ALas Vegas algorithm for linear programming when the dimension is small. In Proc. 29th A nnu. IEEE $ympos. Found. Comput. $c~., pages 452- 456, 1988.
• 18: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 19: Kenneth L. Clarkson, Algorithms for Polytope Covering and Approximation, Proceedings of the Third Workshop on Algorithms and Data Structures, p.246-252, August 11-13, 1993
• 20: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 21: Gautam Das , Deborah A. Joseph, Approximation schemes in computational geometry, 1990
• 22: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 23: Michael T. Goodrich, Geometric partitioning made easier, even in parallel, Proceedings of the ninth annual symposium on Computational geometry, p.73-82, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161002]
• 24: D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Dzscrete Comput. Geom., 2:127-151, 1987.
• 25: D. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput., 11(3):555-556, 1982.
• 26: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 27: D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci., 9:256-278, 1974.
• 28: R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, New York, 1972.
• 29: János Komlós , János Pach , Gerhard Woeginger, Almost tight bounds for &egr;-nets, Discrete & Computational Geometry, v.7 n.2, p.163-173, 1992 [doi>10.1007/BF02187833]
• 30: N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithms. In Proc. 28th IEEE Sympos. Found. of Comput. Sci., pages 68-77, 1987.
• 31: L. Lov~sz. On the ratio of optimal integral and fractional covers. Discrete Math., 13:383-390, 1975.
• 32: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
• 33: Jiří Matoušek, Construction of &egr;-nets, Discrete & Computational Geometry, v.5 n.5, p.427-448, 1990 [doi>10.1007/BF02187804]
• 34: Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
• 35: Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
• 36: Jiří Matoušek, Range searching with efficient hierarchical cuttings, Proceedings of the eighth annual symposium on Computational geometry, p.276-285, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142732]
• 37: Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
• 38: Jiří Matoušek , Raimund Seidel , E. Welzl, How to net a lot with little: small &egr;-nets for disks and halfspaces, Proceedings of the sixth annual symposium on Computational geometry, p.16-22, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98530]
• 39: Jiří Matoušek , Emo Welzl , Lorenz Wernisch, Discrepancy and &egr; approximations for bounded VC-dimension, Proceedings of the 32nd annual symposium on Foundations of computer science, p.424-430, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185401]
• 40: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 41: Joseph S. B. Mitchell , Subhash Suri, Separation and approximation of polyhedral objects, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.296-306, September 1992, Orlando, Florida, United States
• 42: N. Sauer. On the densities of families of sets. Journal of Combinatomal Theory, 13:145-147, 1972.
• 43: V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264-280, 1971.
• 44: E. Welzl, Partition trees for triangle counting and other range searching problems, Proceedings of the fourth annual symposium on Computational geometry, p.23-33, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73397]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Experimentation, Theory, Verification