首页 | 本学科首页   官方微博 | 高级检索  
     


Upper bound for the approximation ratio of a class of hypercube segmentation algorithms
Authors:Jouni K. Seppä  nen
Affiliation:HIIT Basic Research Unit, Laboratory of Computer and Information Science, P.O. Box 5400, FI-02015 Helsinki University of Technology, Finland
Abstract:The Hypercube Segmentation problem was recently introduced by Kleinberg et al. [J. ACM 51 (2004) 263-280], along with several algorithms that select each segment's prototype vector from the segment. The algorithms were shown to have an approximation ratio of at least View the MathML source. We show that a lemma used in this proof is tight, and that the asymptotic approximation ratio of no algorithm of this type can exceed 5/6≈0.833.
Keywords:Approximation algorithms   Combinatorial problems   Clustering   Data mining
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号