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 . 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 等数据库收录! |