RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii

Diskretn. Anal. Issled. Oper., 2023, Volume 30, Issue 3, Pages 96–110 (Mi da1329)

Ptas for problems of vector choice and clustering with different centers
A. V. Pyatkin

References

1. Berkhin P., “A survey of clustering data mining techniques”, Grouping multidimensional data: Recent advances in clustering, Springer, Heidelberg, 2006, 25–71  crossref
2. Jain A. K., Dubes R. C., Algorithms for clustering data, Prentice Hall, Englewood Cliffs, NJ, 1988  mathscinet  zmath
3. Ghoreyshi S., Hosseinkhani J., “Developing a clustering model based on \text{$K$-means} algorithm in order to creating different policies for policyholders”, Int. J. Adv. Comput. Sci. Inf. Tech., 4:2 (2015), 46–53
4. Fisher W. D., “On grouping for maximum homogeneity”, J. Am. Stat. Assoc., 53:284 (1958), 789–798  crossref  mathscinet  zmath
5. MacQueen J., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Mathematics, Statistics and Probability (Berkeley, USA, June 21 — July 18, 1965; Dec. 27, 1965 — Jan. 7, 1966), v. 1, Univ. California Press, Berkeley, 1967, 281–297  mathscinet  zmath
6. Kaufman L., Rousseeuw P. J., “Clustering by means of medoids”, Statistical data analysis based on the $L_1$-norm, North-Holland, Amsterdam, 1987, 405–416  mathscinet
7. Aloise D., Deshpande A., Hansen P., Popat P., “NP-hardness of Euclidean sum-of-squares clustering”, Mach. Learn., 75:2 (2009), 245–248  crossref  zmath
8. Inaba M., Katoh N., Imai H., “Applications of weighted Voronoi diagrams and randomization to variance-based $k$-clustering”, Proc. 10th Annu. Symp. Computational Geometry (Stony Brook, NY, USA, June 6–8, 1994), ACM Press, New York, 1994, 332–339
9. Kumar A., Sabharwal Y., Sen S., “A simple linear time $(1+\varepsilon)$-approximation algorithm for geometric $k$-means clustering in any dimensions”, Proc. 45th Annu. IEEE Symp. Foundations of Computer Science (Rome, Italy, Oct. 17–19, 2004), IEEE Comp. Soc., Los Alamitos, CA, 2004, 454–462  crossref
10. A. E. Baburin, É. Kh. Gimadi, N. I. Glebov, and A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Ind. Math., 2:1 (2008), 32–38  mathnet  crossref  mathscinet  zmath
11. É. Kh. Gimadi, A. V. Kel'manov, M. A. Kel'manova, and S. A. Khamidullin, “A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence”, Sib. Zh. Ind. Mat., 9:1 (2006), 55–74  mathnet  mathscinet  zmath
12. A. V. Kel'manov and A. V. Pyatkin, “On the complexity of a search for a subset of «similar» vectors”, Dokl. Math., 78:1 (2008), 574–575  mathnet  crossref  mathscinet  zmath
13. A. V. Kel'manov and A. V. Pyatkin, “On a version of the problem of choosing a vector subset”, J. Appl. Ind. Math., 3:4 (2009), 447–455  mathnet  crossref  mathscinet  zmath
14. A. V. Dolgushev and A. V. Kel'manov, “An approximation algorithm for solving a problem of cluster analysis”, J. Appl. Ind. Math., 5:4 (2011), 551–558  mathnet  crossref  mathscinet  mathscinet  zmath
15. A. V. Kel'manov and V. I. Khandeev, “A $2$-approximation polynomial algorithm for a clustering problem”, J. Appl. Ind. Math., 7:4 (2013), 515–521  mathnet  crossref  mathscinet  zmath
16. A. V. Dolgushev, A. V. Kel'manov, and V. V. Shenmaier, “A polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Proc. Steklov Inst. Math., 295, Suppl. 1 (2016), 47–56  mathnet  crossref  mathscinet
17. A. V. Kel'manov, A. V. Pyatkin, and V. I. Khandeev, “NP-hardness of quadratic Euclidean $1$-mean and $1$-median $2$-clustering problem with constraints on the cluster sizes”, Dokl. Math., 100:3 (2019), 545–548  crossref  crossref  mathscinet  zmath
18. Pyatkin A. V., “1-Mean and 1-medoid 2-clustering problem with arbitrary cluster sizes: Complexity and approximation”, Yugoslav J. Oper. Res., 33:1 (2023), 59–69  crossref  mathscinet
19. V. V. Shenmaier, “An approximation scheme for a problem of search for a vector subset”, J. Appl. Ind. Math., 6:3 (2012), 381–386  mathnet  crossref  mathscinet  zmath
20. A. E. Galashov and A. V. Kel'manov, “A $2$-approximate algorithm to solve one problem of a family of disjoint vector subsets”, Autom. Remote Control, 75:4 (2014), 595–606  mathnet  crossref  mathscinet  zmath
21. Edmonds J., Karp R. M., “Theoretical improvements in algorithmic efficiency for network flow problems”, J. ACM, 19:2 (1972), 248–264  crossref  mathscinet  zmath
22. Gabow H. N., Tarjan R. E., “Faster scaling algorithms for network problems”, SIAM J. Comput., 18:5 (1989), 1013–1036  crossref  mathscinet  zmath
23. Wirth H., Algorithms + data structures = programs, Prentice Hall, Englewood Cliffs, NJ, 1976  mathscinet


© Steklov Math. Inst. of RAS, 2025