Geodesic
Fast Approximation Algorithms for Some Maximin Clustering Problems
Yugoslav journal of operations research, Tome 34 (2024) no. 2, p. 337 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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.
Classification : 90C27 90C59
Keywords: Euclidean space, clustering, max-min problem, NP-hardness, bounded scatter, approximation algorithm 
@article{YJOR_2024_34_2_a6,
     author = {V. Khandeev and S. Neshchadim},
     title = {Fast {Approximation} {Algorithms} for {Some} {Maximin} {Clustering} {Problems}},
     journal = {Yugoslav journal of operations research},
     pages = {337 },
     publisher = {mathdoc},
     volume = {34},
     number = {2},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2024_34_2_a6/}
}
TY  - JOUR
AU  - V. Khandeev
AU  - S. Neshchadim
TI  - Fast Approximation Algorithms for Some Maximin Clustering Problems
JO  - Yugoslav journal of operations research
PY  - 2024
SP  - 337 
VL  - 34
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2024_34_2_a6/
LA  - en
ID  - YJOR_2024_34_2_a6
ER  - 
%0 Journal Article
%A V. Khandeev
%A S. Neshchadim
%T Fast Approximation Algorithms for Some Maximin Clustering Problems
%J Yugoslav journal of operations research
%D 2024
%P 337 
%V 34
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2024_34_2_a6/
%G en
%F YJOR_2024_34_2_a6
V. Khandeev; S. Neshchadim. Fast Approximation Algorithms for Some Maximin Clustering Problems. Yugoslav journal of operations research, Tome 34 (2024) no. 2, p. 337 . http://geodesic.mathdoc.fr/item/YJOR_2024_34_2_a6/