A new randomized algorithm to approximate the star discrepancy based on threshold accepting (Q2903013)

Star discrepancy measures the irregularity of a given point set. It is an important notion in numerical analysis, since worst-case approximation guarantees of quasi-Monte Carlo integration algorithms can be expressed in terms of the star discrepancy. Unfortunately, it turns out that computing the star discrepancy of a given point set is a provably difficult task (it is known to be NP-hard and even W[1]-hard in the dimension). Several heuristics for approximating the star discrepancy have been developed. The authors of the paper under review present a new such approach. The algorithm is based on a so-called threshold accepting heuristic. It builds on previous work of \textit{P. Winker} and \textit{K.-T. Fang} [SIAM J. Numer. Anal. 34, No. 5, 2028--2042 (1997; Zbl 0888.65021)] and adds to it several new ideas to improve the approximation quality. Some of these ideas yield provably better results, e.g., the concept of so-called \textit{critical test boxes}. Experimental studies are conducted to show that the presented algorithm approximates the star discrepancy values much better than previous works. In particular for medium and large dimensions (experiments for up to 50 dimensions are reported) the quality of the new heuristic clearly outperforms existing methods.