Geodesic
FPTAS for solving a~problem of search for a~vector subset
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 41-52.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider one NP-hard problem of searching for a vector subset in a given finite Euclidean vector set. It is assumed that the desired subset has a fixed cardinality and contains vectors close to the subset center under the criterion of the minimum sum-of-squared distances. The subset center is defined as the mean value of elements of required subsets. We prove that (unless P$=$NP) there are no fully polynomial time approximation scheme (FPTAS) for the general case of the problem. FPTAS for the case of fixed space dimension is presented. Bibliogr. 12.
Keywords: search for a vector subset, Euclidean space, minimum sum-of-squared distances, NP-hardness, FPTAS. 
@article{DA_2014_21_3_a4,
     author = {A. V. Kel'manov and S. M. Romanchenko},
     title = {FPTAS for solving a~problem of search for a~vector subset},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {41--52},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_3_a4/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - S. M. Romanchenko
TI  - FPTAS for solving a~problem of search for a~vector subset
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 41
EP  - 52
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_3_a4/
LA  - ru
ID  - DA_2014_21_3_a4
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A S. M. Romanchenko
%T FPTAS for solving a~problem of search for a~vector subset
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 41-52
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_3_a4/
%G ru
%F DA_2014_21_3_a4
A. V. Kel'manov; S. M. Romanchenko. FPTAS for solving a~problem of search for a~vector subset. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 41-52. http://geodesic.mathdoc.fr/item/DA_2014_21_3_a4/

[1] Kel'manov A. V., Pyatkin A. V., “NP-completeness of some problems of choosing a vector subset”, J. Appl. Industr. Math., 5:3 (2011), 352–357 | DOI | MR | Zbl

[2] Kel'manov A. V., Romanchenko S. M., “An approximation algorithm for solving a problem of search for a vector subset”, J. Appl. Industr. Math., 6:1 (2012), 90–96 | MR | Zbl

[3] Kel'manov A. V., Romanchenko S. M., “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems”, Automation and Remote Control, 73:2 (2012), 349–354 | DOI

[4] Shenmaier V. V., “An approximation scheme for a problem of search for a vector subset”, J. Appl. Industr. Math., 6:3 (2012), 381–386 | DOI | MR

[5] Aloise D., Deshpande A., Hansen P., Popat P., NP-hardness of Euclidean sum-of-squares clustering, G-2008-33, Les Cahiers du GERAD, 2008, 4 pp.

[6] Anil K. Jain K., “Data clustering: 50 years beyond $k$-means”, Pattern Recogn. Lett., 31 (2010), 651–666

[7] Garey M. R., Johnson D. S., Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979, 314 pp. | MR | Zbl

[8] Hastie T., Tibshirani R., Friedman J., The elements of statistical learning: data mining, inference, and prediction, Springer-Verl., New York, 2001, 533 pp. | MR | Zbl

[9] MacQueen J. B., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Math. Statist. Probab. (Berkeley, June 21 – July 18, 1965; December 27, 1965 – January 7, 1966), v. 1, University of California Press, Berkeley, 1967, 281–297 | MR | Zbl

[10] Papadimitriou C. H., Computational complexity, Addison-Wesley, New York, 1994, 523 pp. | MR | Zbl

[11] Rao M., “Cluster analysis and mathematical programming”, J. Amer. Stat. Assoc., 66 (1971), 622–626 | DOI | Zbl

[12] Wirth H., Algorithms+data structures=programs, Prentice Hall, New Jersey, 1976, 366 pp. | MR | Zbl