Almost tight bounds for $\epsilon$-nets

J. Komlós; J. Pach; G.J. Woeginger

doi:10.1007/BF02187833

Almost tight bounds for $\epsilon$-nets

J. Komlós, J. Pach, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

83 Citaten (Scopus)

Samenvatting

Given any natural numberd, 0<d - 2 + \frac2d + 2 \leqslant lime® 0 \fracfd (e)(1/e)log(1/e) \leqslant d.Unknown control sequence '\leqslant' Further, we prove thatf 1()=max(2, 1/ –1), and similar bounds are established for some special classes of range spaces of Vapnik-Chervonenkis dimension three.

Originele taal-2	Engels
Pagina's (van-tot)	163-173
Aantal pagina's	11
Tijdschrift	Discrete and Computational Geometry
Volume	7
Nummer van het tijdschrift	1
DOI's	https://doi.org/10.1007/BF02187833
Status	Gepubliceerd - 1992

Toegang tot document

10.1007/BF02187833

Vingerafdruk Duik in de onderzoeksthema's van 'Almost tight bounds for $\epsilon$-nets'. Samen vormen ze een unieke vingerafdruk.

Citeer dit

@article{eebca84036074458a5ac480c7fef0f4f,

title = "Almost tight bounds for $\epsilon$-nets",

abstract = "Given any natural numberd, 0<d - 2 + \frac2d + 2 \leqslant lime{\textregistered} 0 \fracfd (e)(1/e)log(1/e) \leqslant d.Unknown control sequence '\leqslant' Further, we prove thatf 1()=max(2, 1/ –1), and similar bounds are established for some special classes of range spaces of Vapnik-Chervonenkis dimension three.",

author = "J. Koml{\'o}s and J. Pach and G.J. Woeginger",

year = "1992",

doi = "10.1007/BF02187833",

language = "English",

volume = "7",

pages = "163--173",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Almost tight bounds for $\epsilon$-nets

AU - Komlós, J.

AU - Pach, J.

AU - Woeginger, G.J.

PY - 1992

Y1 - 1992

N2 - Given any natural numberd, 0<d - 2 + \frac2d + 2 \leqslant lime® 0 \fracfd (e)(1/e)log(1/e) \leqslant d.Unknown control sequence '\leqslant' Further, we prove thatf 1()=max(2, 1/ –1), and similar bounds are established for some special classes of range spaces of Vapnik-Chervonenkis dimension three.

AB - Given any natural numberd, 0<d - 2 + \frac2d + 2 \leqslant lime® 0 \fracfd (e)(1/e)log(1/e) \leqslant d.Unknown control sequence '\leqslant' Further, we prove thatf 1()=max(2, 1/ –1), and similar bounds are established for some special classes of range spaces of Vapnik-Chervonenkis dimension three.

U2 - 10.1007/BF02187833

DO - 10.1007/BF02187833

M3 - Article

VL - 7

SP - 163

EP - 173

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 1

ER -