Finding optimal volume subintervals with k points and calculating the star discrepancy are NP-hard problems

被引：38

作者：

Gnewuch, Michael ^{[1
]}

Srivastav, Anand ^{[1
]}

Winzen, Carola ^{[1
]}

机构：

[1] Univ Kiel, Dept Comp Sci, D-24098 Kiel, Germany

来源：

JOURNAL OF COMPLEXITY | 2009年 / 25卷 / 02期

关键词：

Star discrepancy; Complexity; NP-completeness; Computational geometry; COMPUTE BOUNDS; INTEGRATION; ALGORITHM;

D O I：

10.1016/j.jco.2008.10.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The well-known star discrepancy is a common measure for the uniformity of point distributions. It is used, e.g., in multivariate integration, pseudo random number generation, experimental design. statistics, or computer graphics. We study here the complexity of calculating the star discrepancy of point sets in the d-dimensional unit cube and show that this is an NP-hard problem. To establish this complexity result, we first prove NP-hardness of the following related problems in computational geometry: Given n points in the d-dimensional unit cube, find a subinterval Of minimum or maximum volume that contains k of the n points. Our results for the complexity of the subinterval problems settle a conjecture of E. Thiemard [E. Thiemard, Optimal volume subintervals with k points and star discrepancy via integer programming, Math. Meth. Oper. Res. 54 (2001) 21-45]. (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：115 / 127

页数：13

共 31 条

[1]

[Anonymous], 1997, LECT NOTES MATH

[2]

[Anonymous], ANN POL MATH

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[4]

BECK J, 1995, HDB COMBINATORICS, P1405