Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2020) | last year (2019) | two years ago (2018) | Notes URL

Action:

login to update
Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Gnewuch, Michael
Wahlström, Magnus
Winzen, Carola
dblp
dblp
dblp
Not MPG Author(s):

Gnewuch, Michael

BibTeX cite key*:

GnewuchWW12

Title

Title*:

A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting

Journal

Journal Title*:

SIAM Journal on Numerical Analysis
Journal's URL:

http://epubs.siam.org/loi/sjnaam

Download URL
for the article:

http://dx.doi.org/10.1137/110833865
Language:

English

Publisher

Publisher's
Name:

SIAM
Publisher's URL:

http://epubs.siam.org/

Publisher's
Address:

Philadelphia, PA
ISSN:

1095-7170

Vol, No, pp, Date

Volume*:

50
Number:

2

Publishing Date:

April 2012

Pages*:

781-807
Number of
VG Pages:


Page Start:

781
Page End:

807

Sequence Number:


DOI:

10.1137/110833865

Note, Abstract, ©

Note:

Also available from arxiv.

(LaTeX) Abstract:

We present a new algorithm for estimating the star discrepancy of arbitrary point
sets. Similar to the algorithm for discrepancy approximation of Winker and Fang [SIAM J. Numer.
Anal., 34 (1997), pp. 2028–2042] it is based on the optimization algorithm threshold accepting. Our
improvements include, amongst others, a nonuniform sampling strategy, which is more suited for
higher-dimensional inputs and additionally takes into account the topological characteristics of given
point sets, and rounding steps which transform axis-parallel boxes, on which the discrepancy is to be
tested, into critical test boxes. These critical test boxes provably yield higher discrepancy values and
contain the box that exhibits the maximum value of the local discrepancy. We provide comprehensive
experiments to test the new algorithm. Our randomized algorithm computes the exact discrepancy
frequently in all cases where this can be checked (i.e., where the exact discrepancy of the point set
can be computed in feasible time). Most importantly, in higher dimensions the new method behaves
clearly better than all previously known methods.

URL for the Abstract:

http://epubs.siam.org/action/showAbstract?page=781&volume=50&issue=2&journalCode=sjnaam

Categories,
Keywords:

computational geometry, discrepancy, integer programming, numerical integration, optimization heuristics, threshold accepting

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{GnewuchWW12,
AUTHOR = {Gnewuch, Michael and Wahlstr{\"o}m, Magnus and Winzen, Carola},
 TITLE = {A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting},
 JOURNAL = {SIAM Journal on Numerical Analysis},
 PUBLISHER = {SIAM},
 YEAR = {2012},
 NUMBER = {2},
 VOLUME = {50},
 PAGES = {781--807},
 ADDRESS = {Philadelphia, PA},
 MONTH = {April},
 ISBN = {1095-7170},
 DOI = {10.1137/110833865},
 NOTE = {Also available from arxiv.},
}

Entry last modified by Anja Becker, 02/04/2013
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
11/14/2012 05:28:09 PM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Anja Becker
Carola Winzen
Carola Winzen
Carola Winzen
Carola Winzen		Edit Dates
04.02.2013 13:42:19
11/14/2012 05:33:27 PM
11/14/2012 05:32:49 PM
11/14/2012 05:29:12 PM
11/14/2012 05:28:09 PM