Lattice algorithms for multivariate L_∞ approximation in the worst-case setting

We approximate d-variate functions from weighted Korobov spaces with the error of approximation defined in the L_∞ sense. We study lattice algorithms and consider the worst-case setting in which the error is defined by its worst-case behavior over the unit ball of the space of functions. A lattice algorithm is specified by a generating (integer) vector. We propose three choices of such vectors, each corresponding to a different search criterion in the component-by-component construction. We present worst-case error bounds that go to zero polynomially with n^-1, where n is the number of function values used by the lattice algorithm. Under some assumptions on the weights of the function space, the worst-case error bounds are also polynomial in d, in which case we have (polynomial) tractability, or even independent of d, in which case we have strong (polynomial) tractability. We discuss the exponents of n^-1 and stress that we do not know if these exponents can be improved.