Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
type: Item
instance of: scholarly article
title: Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems
zbMATH Open document ID: 1167.65015
author: Michael Gnewuch
author: Anand Srivastav
author: Carola Winzen
published in: Journal of Complexity
publication date: 2009-06-11T00:00:00Z
review text: Star discrepancy is a common measure for the uniformity of point distributions. The authors study the complexity of calculating the star discrepancy of point sets in \(d\)-dimensional unit cube and show that this is an NP-hard problem, The results of the authors for the complexity of the subinterval problems settle a conjecture of \textit{E. Thiémard} [Math. Methods Oper. Res. 54, No.~1, 21--45 (2001; Zbl 1031.90016)]. Some errors in the paper cited above have also been pointed out which may lead to incorrect solutions of Thiémard's algorithm in certain instances. The authors also show how to avoid the undesired consequences of these errors.
reviewed by: H. P. Dikshit
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 5564311
zbMATH Keywords: star discrepancy
zbMATH Keywords: complexity
zbMATH Keywords: NP-completeness
zbMATH Keywords: computational geometry
MaRDI profile type: Publication
full work available at URL: j.jco.2008.10.001
OpenAlex ID: W2162820178
cites work: Q4871774
cites work: Q4515159
cites work: Q3504230
cites work: Component-by-component construction of low-discrepancy point sets of small size
cites work: Bounds and constructions for the star-discrepancy via \(\delta\)-covers
cites work: Sequences, discrepancies and applications
cites work: Q4326423
cites work: Computing discrepancies of Smolyak quadrature rules
cites work: Q4198056
cites work: Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
cites work: Efficient algorithms for computing the $L_2$-discrepancy
cites work: The inverse of the star-discrepancy depends linearly on the dimension
cites work: On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
cites work: Funktionen von beschränkter Variation in der Theorie der Gleichverteilung
cites work: Algorithmics for hard problems.
cites work: The NP-completeness column: An ongoing guide
cites work: Geometric discrepancy. An illustrated guide
cites work: Discrepancy and convex programming
cites work: Q4003879
cites work: Relaxed verification for continuous problems
cites work: When are integration and discrepancy tractable?
cites work: A note on E. Thiémard's algorithm to compute bounds for the star discrepancy
cites work: Computing bounds for the star discrepancy
cites work: An algorithm to compute bounds for the star discrepancy
cites work: Optimal volume subintervals with \(k\) points and star discrepancy via integer programming
cites work: Q5661070
cites work: Application of Threshold-Accepting to the Evaluation of the Discrepancy of a Set of Points
cites work: Some applications of multidimensional integration by parts
DOI: 10.1016/J.JCO.2008.10.001
description: scientific article; zbMATH DE number 5564311