An approximation scheme for a problem of search for a vector subset |
| |
Authors: | V V Shenmaier |
| |
Institution: | 1.Sobolev Institute of Mathematics,Novosibirsk,Russia |
| |
Abstract: | We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n 2/?+1(9/?)3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|