Thumbnail
Access Restriction
Open

Author Ratsa, Joel
Source CiteSeerX
Content type Text
Publisher Birkhäuser Verlag
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Integer Partition ♦ Non-negative Integer ♦ Tight Upper Bound ♦ Sauer Lemma ♦ Several Class ♦ Constrained Version ♦ Finite Vc-dimension Class ♦ Closed-form Estimate ♦ Whole Domain ♦ Binary Function ♦ Key Word
Description 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 non-negative 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. Key words: Sauer’s Lemma, Integer partitions, Binary functions 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2004-01-01
Publisher Institution In Algorithms, Trees Combinatorics and Probabilities, volume III of Mathematics and Computer Science