074  Berichtsreihe des Mathematischen Seminars der Universität Kiel  
Michael Gnewuch:Bracketing numbers for axisparallel boxes and applications to geometric discrepancyIn the first part of this paper we derive lower bounds and constructive upper bounds for the bracketing numbers of anchored and unanchored axisparallel boxes in the ddimensional unit cube. In the second part we apply these results to geometric discrepancy. We derive upper bounds for the inverse of the star and the extreme discrepancy with explicitly given small constants and an optimal dependence on the dimension d, and provide corresponding bounds for the star and the extreme discrepancy itself. These bounds improve known results from [B. Doerr, M. Gnewuch, A. Srivastav. Bounds and constructions for the stardiscrepancy via δcovers. J. Complexity 21 (2005), 691709], [M. Gnewuch. Bounds for the average L^{p}extreme and the L^{∞}extreme discrepancy, Electron. J. Combin. 12 (2005), Research Paper 54] and [H. N. Mhaskar. On the tractibility of multivariate integration and approximation by neural networks. J. Complexity 20 (2004), 561590]. We also discuss an algorithm from [E. Thiemard, An algorithm to compute bounds for the star discrepancy, J. Complexity 17 (2001), 850880] to approximate the stardiscrepancy of a given npoint set. Our lower bound on the bracketing number of anchored boxes, e.g., leads directly to a lower bound of the running time of Thiemard's algorithm. Furthermore, we show how one can use our results to modify the algorithm to approximate the extreme discrepancy of a given set. Mathematics Subject Classification (1991): 11K38 Bibliographical note: Journal of Complexity 24 (2008), 154172 Keywords: star discrepancy, extreme discrepancy, bracketing number, covering number, metric entropy

Mail an Jens Burmeister 
[Thu Feb 19 18:56:37 2009] 
Impressum 