EN|RU
English version: Journal of Applied and Industrial Mathematics, 2020, 14:2, 242-248 |
![]() |
Volume 27, No 2, 2020, P. 5-16 UDC 519.254
Keywords: NP-hard problem, typical representative, rival similarity, $p$-median problem, data mining. DOI: 10.33048/daio.2020.27.631 Irina A. Borisova 1,2 Received September 10, 2018 References[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).[2] D. Aloise, A. Deshpande, P. Hansen, and P. Popat, NP-hardness of Euclidean sum-of-squares clustering, Mach. Learn. 75 (2), 245–248 (2009). [3] S. Dasgupta, The hardness of $k$-means clustering, in Technical report CS2007-0890 (Univ. California, San Diego, 2008), pp. 1–6. [4] C. H. Papadimitriou, Worst-case and probabilistic analysis of a geometric location problem, SIAM J. Comput. 10 (3), 542–557 (1981). [5] S. Har-Peled and S. Mazumdar, Coresets for k-means and k-median clustering and their applications, in Proc. 36th Annu. ACM Sympos. Theory Comput., Chicago, IL, USA, June 13–15, 2004 (ACM, New York, 2004), pp. 291–300. [6] L. Kaufman and P. J. Rousseeuw, Clustering by means of medoids, in Statistical Data Analysis Based on the $L_1$-Norm and Related Methods (North Holland, Amsterdam, 1987), pp. 405–416. [7] A. V. Kel’manov, A. V. Pyatkin, and V. I. Khandeev, On the complexity of some max–min clustering problems, Tr. Inst. Mat. Mekh. UrO RAN 24 (4), 189–198 (2018) [Russian]. [8] A. V. Kel’manov and A. V. Pyatkin, NP-hardness of some Euclidean problems of partition of a finite set of points, Zh. Vychisl. Mat. Mat. Fiz. 58 (5), 852–856 (2018) [Russian]. [9] H. Aggarwal, N. Imai, N. Katoh, and S. Suri, Finding k points with minimum diameter and related problems, J. Algorithms 12 (1), 38–56 (1991). [10] A. V. Zukhba, NP-completeness of the problem of prototype selection in the nearest neighbor method, Pattern Recognit. Image Anal. 20 (4), 484–494 (2010). [11] S. Banerjee, S. Bhore, and R. Chitnis, Algorithms and hardness results for nearest neighbor problems in bicolored point sets, in Proc. 13th Latin Amer. Theor. Inform. Symp., Buenos Aires, Argentina, Apr. 16–19, 2018 (Springer, Cham, 2018), pp. 80–93 (Lect. Notes Comput. Sci., Vol. 10807). [12] V. N. Vapnik, The Restoration of Dependencies from Empirical Data (Nauka, Moscow, 1974) [Russian]. [13] C. J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining Knowl. Discov. 2 (2), 121–167 (1998). [14] N. G. Zagoruiko, I. A. Borisova, V. V. Dyubanov, and O. A. Kutnenko, Methods of recognition based on the function of rival similarity, Pattern Recognit. Image Anal. 18 (1), 1–6 (2008). [15] O. Kariv and S. Hakimi, An algoritmic approach to network location problems. II: The $p$-medians, SIAM J. Appl. Math., 37 (3), 539–560 (1979). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|