Constrained versions of Sauer's lemma

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

Let [n] = {1, ..., n}. For a function h : [n] → {0, 1}, x ∈ [n] and y ∈ {0, 1} define by the widthωh (x, y) of h at x the largest nonnegative integer a such that h (z) = y on x - a ≤ z ≤ x + a. We consider finite VC-dimension classes of functions h constrained to have a width ωh (xi, yi) which is larger than N for all points in a sample ζ = {(xi, yi)}1 or a width no larger than N over the whole domain [n]. Extending Sauer's lemma, a tight upper bound with closed-form estimates is obtained on the cardinality of several such classes.

שפה מקוריתאנגלית
עמודים (מ-עד)2753-2767
מספר עמודים15
כתב עתDiscrete Applied Mathematics
כרך156
מספר גיליון14
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 28 יולי 2008

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Constrained versions of Sauer's lemma'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי