Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems (Q1023397): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jco.2008.10.001 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2162820178 / rank | |||
Normal rank |
Revision as of 21:14, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems |
scientific article |
Statements
Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems (English)
0 references
11 June 2009
0 references
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.
0 references
star discrepancy
0 references
complexity
0 references
NP-completeness
0 references
computational geometry
0 references