ISSN:
1439-6912
Schlagwort(e):
05 C 65
;
52 C 99
;
05 A 05
;
52 C 10
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
Abstract Let (X, ℛ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in ℛ. We show that if for anym-point subset $$Y \subseteq X$$ the number of distinct subsets induced by ℛ onY is bounded byO(m d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n 1/2−1/2d(logn)1+1/2d ). Also if any subcollection ofm sets of ℛ partitions the points into at mostO(m d) classes, then there is a coloring with discrepancy at mostO(n 1/2−1/2dlogn). These bounds imply improved upper bounds on the size of ε-approximations for (X, ℛ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01303517
Permalink
