Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems (Q1023397): Difference between revisions

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.