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

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

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.

langue originale	Anglais
titre	Monte Carlo and Quasi-Monte Carlo Methods 2006
Editeur	Springer Verlag
Pages	299-312
Nombre de pages	14
ISBN (imprimé)	9783540744955
Les DOIs	https://doi.org/10.1007/978-3-540-74496-2_17
état	Publié - 1 janv. 2008
Modification externe	Oui
Evénement	7th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2006 - Ulm, Allemagne Durée: 14 août 2006 → 18 août 2006

Série de publications

Nom	Monte Carlo and Quasi-Monte Carlo Methods 2006

Une conférence

Une conférence	7th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2006
Pays/Territoire	Allemagne
La ville	Ulm
période	14/08/06 → 18/08/06

Accès au document

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

Contient cette citation

@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. Dans Monte Carlo and Quasi-Monte Carlo Methods 2006. Monte Carlo and Quasi-Monte Carlo Methods 2006, Springer Verlag, p. 299-312, 7th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMC 2006, Ulm, Allemagne, 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).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

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

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation