• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Norm statistics and the complexity of clustering problems
【24h】

Norm statistics and the complexity of clustering problems

机译：规范统计和聚类问题的复杂性

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

摘要

In this paper we introduce a new class of clustering problems. These are similar to certain classical problems but involve a novel combination of l(p)-statistics and l(q) norms. We discuss a real world application in which the case p = 2 and q = 1 arises in a natural way. We show that, even for one dimension, such problems are NP-hard, which is surprising because the same 1-dimensional problems for the 'pure' l(2)-statistic and l(2) norm are known to satisfy a 'string property' and can be solved in polynomial time. We generalize the string property for the case p = q. The string property need not hold when q <= p - 1 and we show that instances may be constructed, for which the best solution satisfying the string property does arbitrarily poorly. We state some open problems and conjectures.
机译：在本文中，我们介绍了一类新的聚类问题。这些类似于某些经典问题，但涉及l（p）-统计量和l（q）范数的新颖组合。我们讨论了一个现实世界的应用，其中p = 2和q = 1的情况很自然地出现。我们表明，即使对于一维，此类问题也是NP难的，这是令人惊讶的，因为已知“纯” l（2）-统计量和l（2）范数的相同一维问题都满足“字符串”属性”，可以在多项式时间内求解。对于p = q的情况，我们推广了字符串属性。当q <= p-1时，字符串属性不必成立，我们证明可以构造实例，对于这些实例，满足字符串属性的最佳解决方案的表现会很差。我们陈述一些未解决的问题和猜想。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号