کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4609121 | 1338412 | 2010 | 18 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Algorithmic construction of low-discrepancy point sets via dependent randomized rounding Algorithmic construction of low-discrepancy point sets via dependent randomized rounding](/preview/png/4609121.png)
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.
Journal: Journal of Complexity - Volume 26, Issue 5, October 2010, Pages 490–507