Computing Star Discrepancies

Our improvements include, amongst others, a non-uniform sampling
strategy which is more suited for higher-dimensional inputs and
additionally takes into account the topological characteristics of given point sets, and rounding steps which transform axis-parallel boxes, on which the discrepancy is to be tested, into critical test boxes. These critical test boxes provably yield higher discrepancy values, and contain the box that exhibits the maximum value of the local discrepancy.

We shall also present comprehensive experiments to test the new algorithm. Our randomized algorithm computes the exact
discrepancy frequently in all cases where this can be checked (i.e., where the exact discrepancy of the point set can be computed in feasible time). Most importantly, in higher dimension the new method behaves clearly better than all previously known methods.

The talk is based on results presented in [1].

[1] M. Gnewuch, Magnus Wahlström, and C. Winzen.
A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting.
SIAM Journal on Numerical Analysis, to appear.

[2] P. Winker and K.T. Fang.
Applications of threshold-accepting to the evaluation of the discrepancy of a set of points. SIAM J. Numer. Anal., 34:2028--2042, 1997.