A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting
A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting
复制标题
DOI：
10.1137/110833865
复制
发表时间：
2012-03
期刊：
影响因子：
--
通讯作者：
M. Gnewuch;Magnus Wahlström;Carola Doerr
中科院分区：
文献类型：
--
作者：
M. Gnewuch;Magnus Wahlström;Carola Doerr
提出了一种估计任意点集的星差的新算法。与Winker和Fang的偏差逼近算法相似[SIAM J.Numer.分析，34(1997)，pp.2028-2042]它是基于优化算法阈值接受的。我们的改进包括，非均匀采样策略，它更适合于高维输入，并且另外考虑了给定点集的拓扑特征，以及舍入步骤，将在其上测试差异的轴平行盒转换为关键测试盒。这些关键测试框可证明会产生较高的差异值，并包含显示局部差异的最大值的框。我们提供了全面的实验来测试新算法。我们的随机化算法在所有可以检查的情况下(即，可以在可行的时间内计算点集的精确差异)频繁地计算精确差异。最重要的是，在更高的维度上，新方法的表现明显好于所有以前已知的方法。
We present a new algorithm for estimating the star discrepancy of arbitrary point sets. Similar to the algorithm for discrepancy approximation of Winker and Fang [SIAM J. Numer. Anal., 34 (1997), pp. 2028-2042] it is based on the optimization algorithm threshold accepting. Our improvements include, amongst others, a nonuniform 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 provide 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 dimensions the new method behaves clearly better than all previously known methods.