Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding

Benjamin Doerr; Michael Gnewuch

doi:10.1007/978-3-540-74496-2_17

Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding

Benjamin Doerr
, Michael Gnewuch

Max-Planck-Institut fur Informatik
Christian-Albrechts-University Kiel

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on bracketing and on recent results on randomized roundings respecting hard constraints. It is structurally much simpler than the previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav. Bounds and constructions for the star discrepancy via d-covers. J. Complexity, 21:691-709, 2005]. Besides leading to better theoretical run time bounds, our approach also can be implemented with reasonable effort.

Original language	English
Title of host publication	Monte Carlo and Quasi-Monte Carlo Methods 2006
Publisher	Springer Verlag
Pages	299-312
Number of pages	14
ISBN (Print)	9783540744955
DOIs	https://doi.org/10.1007/978-3-540-74496-2_17
Publication status	Published - 1 Jan 2008
Externally published	Yes
Event	7th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2006 - Ulm, Germany Duration: 14 Aug 2006 → 18 Aug 2006

Publication series

Name	Monte Carlo and Quasi-Monte Carlo Methods 2006

Conference

Conference	7th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2006
Country/Territory	Germany
City	Ulm
Period	14/08/06 → 18/08/06

Access to Document

10.1007/978-3-540-74496-2_17

Cite this

@inproceedings{68e03d80c23e4797b6e2d8412391c887,

title = "Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding",

abstract = "We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on bracketing and on recent results on randomized roundings respecting hard constraints. It is structurally much simpler than the previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav. Bounds and constructions for the star discrepancy via d-covers. J. Complexity, 21:691-709, 2005]. Besides leading to better theoretical run time bounds, our approach also can be implemented with reasonable effort.",

author = "Benjamin Doerr and Michael Gnewuch",

year = "2008",

month = jan,

day = "1",

doi = "10.1007/978-3-540-74496-2\_17",

language = "English",

isbn = "9783540744955",

series = "Monte Carlo and Quasi-Monte Carlo Methods 2006",

publisher = "Springer Verlag",

pages = "299--312",

booktitle = "Monte Carlo and Quasi-Monte Carlo Methods 2006",

note = "7th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2006 ; Conference date: 14-08-2006 Through 18-08-2006",

}

Doerr, B & Gnewuch, M 2008, Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding. in Monte Carlo and Quasi-Monte Carlo Methods 2006. Monte Carlo and Quasi-Monte Carlo Methods 2006, Springer Verlag, pp. 299-312, 7th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2006, Ulm, Germany, 14/08/06. https://doi.org/10.1007/978-3-540-74496-2_17

Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding. / Doerr, Benjamin; Gnewuch, Michael.
Monte Carlo and Quasi-Monte Carlo Methods 2006. Springer Verlag, 2008. p. 299-312 (Monte Carlo and Quasi-Monte Carlo Methods 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding

AU - Doerr, Benjamin

AU - Gnewuch, Michael

PY - 2008/1/1

Y1 - 2008/1/1

N2 - We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on bracketing and on recent results on randomized roundings respecting hard constraints. It is structurally much simpler than the previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav. Bounds and constructions for the star discrepancy via d-covers. J. Complexity, 21:691-709, 2005]. Besides leading to better theoretical run time bounds, our approach also can be implemented with reasonable effort.

AB - We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on bracketing and on recent results on randomized roundings respecting hard constraints. It is structurally much simpler than the previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav. Bounds and constructions for the star discrepancy via d-covers. J. Complexity, 21:691-709, 2005]. Besides leading to better theoretical run time bounds, our approach also can be implemented with reasonable effort.

U2 - 10.1007/978-3-540-74496-2_17

DO - 10.1007/978-3-540-74496-2_17

M3 - Conference contribution

AN - SCOPUS:47849130683

SN - 9783540744955

T3 - Monte Carlo and Quasi-Monte Carlo Methods 2006

SP - 299

EP - 312

BT - Monte Carlo and Quasi-Monte Carlo Methods 2006

PB - Springer Verlag

T2 - 7th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2006

Y2 - 14 August 2006 through 18 August 2006

ER -

Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this