Tractability properties of the weighted star discrepancy of regular grids
This provides theoretical foundations for understanding the complexity of numerical integration in high dimensions, but the results are incremental and specific to a particular discrepancy measure and grid type.
The paper characterizes weight sequences for which regular grids with different mesh-sizes achieve various tractability properties (weak, uniform weak, quasi-polynomial, polynomial, strong polynomial) for the weighted star discrepancy, providing exact conditions such as \(\lim_{j o \infty} j \gamma_j = 0\) for weak tractability.
In this paper we study tractability properties of the weighted star discrepancy with general coefficients of centered regular grids with different mesh-sizes. We give exact characterizations of the weight sequences $(γ_j)_{j \ge 1}$ such that the regular grid with different mesh-sizes achieves weak, uniform weak, quasi polynomial, polynomial or strong polynomial tractability for the $\boldsymbolγ$-weighted star discrepancy. For example, a necessary and sufficient condition such that the regular grid with different mesh-sizes achieves weak tractability for the $\boldsymbolγ$-weighted star discrepancy is $\lim_{j \rightarrow \infty}j γ_j=0$.