Algorithmic construction of low-discrepancy point sets via dependent randomized rounding

作者：Doerr Benjamin; Gnewuch Michael^*; Wahlstroem Magnus

来源：Journal of Complexity, 2010, 26(5): 490-507.

DOI：10.1016/j.jco.2010.03.004

• Star discrepancy
• Low-discrepancy points
• Randomized rounding
• Derandomization

We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on recent results on randomized roundings respecting hard constraints and their derandomization. It is structurally much simpler than a previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav, Bounds and constructions for the star discrepancy via delta-covers, J. Complexity, 21 (2005) 691-709]. Besides leading to better theoretical running time bounds, our approach also can be implemented with reasonable effort. We implemented this algorithm and performed numerical comparisons with other known low-discrepancy constructions. The experiments take place in dimensions ranging from 5 to 21 and indicate that our algorithm leads to superior results if the dimension is relatively high and the number of points that have to be constructed is rather small.

• 出版日期2010-10