New averaging technique for approximating weighted integrals
We consider a new averaging technique for studying the complexity of weighted multivariate integration problems. While the standard averaging requires that integral(D) K(x, x) rho(x) dx < infinity, our new technique works under a less restrictive condition integral(D) root K(x, x) rho(x) dx < infinity. It allows us to conclude the existence of algorithms with the worst case errors bounded by O(n(-1/2)) for a wider class of problems than the techniques used so far. It also leads to more refined sufficient conditions for tractability of the multivariate integration problems, as well as a new class of randomized algorithms with errors bounded by O(n(-1) root ln(ln(n))). (C) 2009 Elsevier Inc. All rights reserved.
tractability multivariate weighted integration worst case setting randomized setting