TY - JOUR

T1 - FAST APPROXIMATION ALGORITHMS FOR SOME MAXIMIN CLUSTERING PROBLEMS

AU - Khandeev, V.

AU - Neshchadim, S.

N1 - The study was supported by the Russian Academy of Science (the Program of basic research), project FWNF-2022-0015.

PY - 2024

Y1 - 2024

N2 - In this paper, we consider three cases of an intractable problem of searching for two subsets in a finite set of points of Euclidean space. In all three cases, it is required to maximize the minimum cluster’s cardinality under constraint on each cluster’s scatter. The scatter is the sum of the distances from the cluster elements to the center, which is defined differently in each of the three cases. In the first case, cluster centers are fixed points. In the second case, the centers are unknown points from the input set. In the third case, the centers are defined as the centroids (the arithmetic mean) of clusters. We propose a general scheme that allows us to build a polynomial 1/2-approximation algorithm for a generalized problem and can be used for constructing 1/2-approximation algorithms for the first two cases and for the one-dimensional third case. Also we show how, using precomputed general information, their time complexities can be reduced to the complexity of sorting. Finally, we present the results of computational experiments showing the accuracy of the proposed algorithms on randomly generated input data.

AB - In this paper, we consider three cases of an intractable problem of searching for two subsets in a finite set of points of Euclidean space. In all three cases, it is required to maximize the minimum cluster’s cardinality under constraint on each cluster’s scatter. The scatter is the sum of the distances from the cluster elements to the center, which is defined differently in each of the three cases. In the first case, cluster centers are fixed points. In the second case, the centers are unknown points from the input set. In the third case, the centers are defined as the centroids (the arithmetic mean) of clusters. We propose a general scheme that allows us to build a polynomial 1/2-approximation algorithm for a generalized problem and can be used for constructing 1/2-approximation algorithms for the first two cases and for the one-dimensional third case. Also we show how, using precomputed general information, their time complexities can be reduced to the complexity of sorting. Finally, we present the results of computational experiments showing the accuracy of the proposed algorithms on randomly generated input data.

KW - Euclidean space

KW - NP-hardness

KW - approximation algorithm

KW - bounded scatter

KW - clustering

KW - max-min problem

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85195052085&origin=inward&txGid=9a6bdd2d15fbf7d59d6054fbf0a7a193

UR - https://www.mendeley.com/catalogue/553e7448-1445-3213-b274-3689dff52a87/

U2 - 10.2298/YJOR2023021K

DO - 10.2298/YJOR2023021K

M3 - Article

VL - 34

SP - 337

EP - 353

JO - Yugoslav Journal of Operations Research

JF - Yugoslav Journal of Operations Research

SN - 0354-0243

IS - 2

ER -