The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Almost optimal set covers in finite VC-dimension
Open accessOverview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
Computational Geometry--An Introduction.
Atallah, M. J., Preparata, F. P., & Shamos, M. I. (1986) · Mathematics of Computation · doi:10.2307/2008200 · Cited by 4,238
Preparata, F. P., & Shamos, M. I. (1985) · Springer eBooks · doi:10.1007/978-1-4612-1098-6 · Cited by 3,655
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (2015) · Measures of Complexity · doi:10.1007/978-3-319-21852-6_3 · Cited by 3,105
A Greedy Heuristic for the Set-Covering Problem
Chvatal, V. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.3.233 · Cited by 2,581
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (1971) · Theory of Probability & Its Applications · doi:10.1137/1116025 · Cited by 2,448
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,197
Data Structures and Network Algorithms
Tarjan, R. E. (1983) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970265 · Cited by 2,057
Learnability and the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989) · Journal of the ACM · doi:10.1145/76359.76371 · Cited by 1,839
On the ratio of optimal integral and fractional covers
Lovász, L. (1975) · Discrete Mathematics · doi:10.1016/0012-365x(75)90058-8 · Cited by 1,114
On the density of families of sets
Sauer, N. (1972) · Journal of Combinatorial Theory, Series A · doi:10.1016/0097-3165(72)90019-2 · Cited by 844
ɛ-nets and simplex range queries
Haussler, D., & Welzl, E. (1987) · Discrete & Computational Geometry · doi:10.1007/bf02187876 · Cited by 723
Applications of random sampling in computational geometry, II
Clarkson, K. L., & Shor, P. W. (1989) · Discrete & Computational Geometry · doi:10.1007/bf02187740 · Cited by 665
Approximation Algorithms for the Set Covering and Vertex Cover Problems
Hochbaum, D. S. (1982) · SIAM Journal on Computing · doi:10.1137/0211045 · Cited by 506
An optimal convex hull algorithm in any fixed dimension
Chazelle, B. (1993) · Discrete & Computational Geometry · doi:10.1007/bf02573985 · Cited by 385
Efficient probabilistically checkable proofs and applications to approximations
Bellare, M., Goldwasser, S., Lund, C., et al. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167174 · Cited by 317
Cutting hyperplanes for divide-and-conquer
Chazelle, B. (1993) · Discrete & Computational Geometry · doi:10.1007/bf02189314 · Cited by 270
A deterministic view of random sampling and its use in geometry
Chazelle, B., & Friedman, J. (1990) · COMBINATORICA · doi:10.1007/bf02122778 · Cited by 258
Matoušek, J. (1992) · Discrete & Computational Geometry · doi:10.1007/bf02293051 · Cited by 234
Reporting points in halfspaces
Matous̆ek, J. (1992) · Computational Geometry · doi:10.1016/0925-7721(92)90006-e · Cited by 233
On the hardness of approximating minimization problems
Lund, C., & Yannakakis, M. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167172 · Cited by 216
Quasi-optimal range searching in spaces of finite VC-dimension
Chazelle, B., & Welzl, E. (1989) · Discrete & Computational Geometry · doi:10.1007/bf02187743 · Cited by 192
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Littlestone, N. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.37 · Cited by 186
Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. (1986) · Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 · doi:10.1145/12130.12158 · Cited by 159
Komlós, J., Pach, J., & Woeginger, G. J. (1992) · Discrete & Computational Geometry · doi:10.1007/bf02187833 · Cited by 130
Efficient NC algorithms for set cover with applications to learning and geometry
Berger, B., Rompel, J., & Shor, P. W. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80068-6 · Cited by 122
Cutting hyperplane arrangements
Matoušek, J. (1991) · Discrete & Computational Geometry · doi:10.1007/bf02574697 · Cited by 117
Assouad, P. (1983) · Annales de l’institut Fourier · doi:10.5802/aif.938 · Cited by 106
Partition trees for triangle counting and other range searching problems
Welzl, E. (1988) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/73393.73397 · Cited by 102
Matoušek, J. (1990) · Discrete & Computational Geometry · doi:10.1007/bf02187804 · Cited by 83
Discrepancy and approximations for bounded VC-dimension
Matoušek, J., Welzl, E., & Wernisch, L. (1993) · COMBINATORICA · doi:10.1007/bf01303517 · Cited by 81
An optimal convex hull algorithm and new results on cuttings
Chazelle, B. (1991) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1991.185345 · Cited by 79
On learning a union of half spaces
Baum, E. B. (1990) · Journal of Complexity · doi:10.1016/0885-064x(90)90012-3 · Cited by 76
Training a 3-node neural network is NP-complete
Blum, A. L., & Rivest, R. L. (1993) · Lecture notes in computer science · doi:10.1007/3-540-56483-7_20 · Cited by 58
Efficient NC algorithms for set cover with applications to learning and geometry
Berger, B., Rompel, J., & Shor, P. W. (1989) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63455 · Cited by 35
Decision trees for geometric models
Arkin, E. M., Meijer, H., Mitchell, J. S. B., Rappaport, D. D., & Skiena, S. (1993) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/160985.161167 · Cited by 33
Discrepancy and in -approximations for bounded VC-dimension
Matoušek, J., Welzl, E., & Wernisch, L. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1991.185401 · Cited by 33
(1990)
Metadata
- Authors
- Brönnimann, H., & Goodrich, M. T.
- Venue
- Discrete & Computational Geometry
- Published
- 1995-12
- Volume
- 14
- Issue
- 4
- Pages
- 463-479
- ISSN
- 0179-5376 (ISSN-L)
- 1432-0444
- OpenAlex
- W2022671649
- Cited by
- 441
- References
- 40
- FWCI
- 11.73
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
