...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of complexity >Hardness of discrepancy computation and ε-net verification in high dimension
【24h】

Hardness of discrepancy computation and ε-net verification in high dimension

机译：高维差异计算和ε-net验证的难度

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 n~(O(d)), where d is the dimension of the underlying space. As such a dependency on d 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 f(d) • n~(O(1))-time algorithm is possible for any function f(d) 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 2~n.
机译：差异度量点集相对于给定范围集的均匀分布。根据范围，会出现几种变体，包括星号差异，盒子差异和半空间差异。这些问题可以在时间n〜（O（d））中解决，其中d是基础空间的维数。由于对d的依赖对于高维数据变得难以处理，因此我们问是否可以缓和它。我们通过证明标准决策问题相对于维为W [1]-来否定地回答这个问题，这意味着对于任何函数f都没有f（d）•n〜（O（1））-时间算法是可能的（d）除非FPT-W [1]。我们还发现了其他众所周知的问题的W [1] -hardness，例如确定包含原点且位于单位立方体内部的最大空盒子。这被证明甚至很难在2〜n的范围内逼近。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号