Construction of Low-discrepancy Point Sets of Small Size by Bracketing Covers 
and Dependent Randomized Rounding

Doerr, Benjamin; Gnewuch, Michael

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

Construction of Low-discrepancy Point Sets of Small Size by Bracketing Covers and Dependent Randomized Rounding

MPS-Authors

/persons/resource/persons44338

Doerr, Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Doerr, B., & Gnewuch, M.(2006). Construction of Low-discrepancy Point Sets of Small Size by Bracketing Covers and Dependent Randomized Rounding (06-14). Kiel: University Kiel.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-E49F-6

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 -covers. J. Complexity, 21: 691-709, 2005]. Besides leading to better theoretical run time bounds, our approach can be implemented with reasonable effort.