Algorithmic construction of low-discrepancy point sets via dependent randomized rounding |
| |
Authors: | Benjamin Doerr Michael Gnewuch Magnus Wahlström |
| |
Institution: | 1. Max-Planck-Institut für Informatik, Campus E1 4, 66123 Saarbrücken, Germany;2. Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Christian-Albrechts-Platz 4, 24098 Kiel, Germany;3. Department of Computer Science, Columbia University, 1214 Amsterdam Avenue, New York, NY 10027, USA |
| |
Abstract: | 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 δ-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. |
| |
Keywords: | Star discrepancy Low-discrepancy points Randomized rounding Derandomization |
本文献已被 ScienceDirect 等数据库收录! |
|