Hardness of discrepancy computation and -net verification in high dimension

详细信息	查看全文 | 推荐本文 |

• 作者：Panos Giannopoulos^a ; ^{panos@inf.fu-berlin.de} ; ^{panos@mi.fu-berlin.de} ; Christian Knauer^b ; ^{christian.knauer@uni-bayreuth.de} ; Magnus Wahlströ ; m^c ; ^{wahl@mpi-inf.mpg.de} ; Daniel Werner^a ; ^{daniel.werner@fu-berlin.de}
• 关键词：Discrepancy ; Epsilon-nets ; Geometric dimension ; Parameterized complexity ; Inapproximability
• 刊名：Journal of Complexity
• 出版年：2012
• 期刊代码：73_0885064x
• 类别：mt
• 出版时间：April, 2012
• 卷：28
• 期：2
• 页码：162-176
• 文件大小：344 K

摘要

Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. Depending on the ranges, several variants arise, including star discrepancy, box discrepancy, and discrepancy of halfspaces. These problems are solvable in time , where is the dimension of the underlying space. As such a dependency on becomes intractable for high-dimensional data, we ask whether it can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension, implying that no -time algorithm is possible for any function unless FPT=W[1]. We also discover the W[1]-hardness of other well known problems, such as determining the largest empty box that contains the origin and is inside the unit cube. This is shown to be hard even to approximate within a factor of .