An FPTAS for a vector subset search problem |
| |
Authors: | A V Kel’manov S M Romanchenko |
| |
Institution: | 1. Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia 2. Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia
|
| |
Abstract: | Under study is a strongly NP-hard problem of finding a subset of a given size of a finite set of vectors in Euclidean space which minimizes the sum of squared distances from the elements of this subset to its center. The center of the subset is defined as the average vector calculated with all subset elements. It is proved that, unless P=NP, in the general case of the problem there is no fully polynomial time approximation scheme (FPTAS). Such a scheme is provided in the case when the dimension of the space is fixed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|