Standard

Approximate Algorithms for Some Maximin Clustering Problems. / Khandeev, Vladimir; Neshchadim, Sergey.

Mathematical Optimization Theory and Operations Research: Recent Trends - 21st International Conference, MOTOR 2022, Revised Selected Papers. ред. / Yury Kochetov; Anton Eremeev; Oleg Khamisov; Anna Rettieva. Springer Science and Business Media Deutschland GmbH, 2022. стр. 89-103 (Communications in Computer and Information Science; Том 1661 CCIS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Khandeev, V & Neshchadim, S 2022, Approximate Algorithms for Some Maximin Clustering Problems. в Y Kochetov, A Eremeev, O Khamisov & A Rettieva (ред.), Mathematical Optimization Theory and Operations Research: Recent Trends - 21st International Conference, MOTOR 2022, Revised Selected Papers. Communications in Computer and Information Science, Том. 1661 CCIS, Springer Science and Business Media Deutschland GmbH, стр. 89-103, 21st International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2022, Petrozavodsk, Российская Федерация, 02.07.2022. https://doi.org/10.1007/978-3-031-16224-4_6

APA

Khandeev, V., & Neshchadim, S. (2022). Approximate Algorithms for Some Maximin Clustering Problems. в Y. Kochetov, A. Eremeev, O. Khamisov, & A. Rettieva (Ред.), Mathematical Optimization Theory and Operations Research: Recent Trends - 21st International Conference, MOTOR 2022, Revised Selected Papers (стр. 89-103). (Communications in Computer and Information Science; Том 1661 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-16224-4_6

Vancouver

Khandeev V, Neshchadim S. Approximate Algorithms for Some Maximin Clustering Problems. в Kochetov Y, Eremeev A, Khamisov O, Rettieva A, Редакторы, Mathematical Optimization Theory and Operations Research: Recent Trends - 21st International Conference, MOTOR 2022, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2022. стр. 89-103. (Communications in Computer and Information Science). doi: 10.1007/978-3-031-16224-4_6

Author

Khandeev, Vladimir ; Neshchadim, Sergey. / Approximate Algorithms for Some Maximin Clustering Problems. Mathematical Optimization Theory and Operations Research: Recent Trends - 21st International Conference, MOTOR 2022, Revised Selected Papers. Редактор / Yury Kochetov ; Anton Eremeev ; Oleg Khamisov ; Anna Rettieva. Springer Science and Business Media Deutschland GmbH, 2022. стр. 89-103 (Communications in Computer and Information Science).

BibTeX

@inproceedings{298410787b8146aba4ead0cfd704c4b7,
title = "Approximate Algorithms for Some Maximin Clustering Problems",
abstract = "In this paper we consider three problems of searching for disjoint subsets among a finite set of points in an Euclidean space. In all three problems, it is required to maximize the size of the minimal cluster so that each intra-cluster scatter of points relative to the cluster center does not exceed a predetermined threshold. In the first problem, the centers of the clusters are given as input. In the second problem, the centers are unknown, but belong to the initial set. In the last problem, the center of each cluster is defined as the arithmetic mean of all its elements. It is known that all three problems are NP-hard even in the one-dimensional case. The main result of the work is constant-factor approximation algorithms for all three problems. For the first two problems, 1/2-approximate algorithms for an arbitrary space dimension are constructed. Also we propose a 1/2-approximate algorithm for the one-dimensional case of the third problem.",
keywords = "Approximation algorithm, Bounded scatter, Clustering, Euclidean space, Max-min problem, NP-hardness",
author = "Vladimir Khandeev and Sergey Neshchadim",
note = "Funding Information: Acknowledgments. The study presented was supported by the Russian Academy of Science (the Program of basic research), project FWNF-2022-0015. Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 21st International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2022 ; Conference date: 02-07-2022 Through 06-07-2022",
year = "2022",
doi = "10.1007/978-3-031-16224-4_6",
language = "English",
isbn = "9783031162237",
series = "Communications in Computer and Information Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "89--103",
editor = "Yury Kochetov and Anton Eremeev and Oleg Khamisov and Anna Rettieva",
booktitle = "Mathematical Optimization Theory and Operations Research",
address = "Germany",

}

RIS

TY - GEN

T1 - Approximate Algorithms for Some Maximin Clustering Problems

AU - Khandeev, Vladimir

AU - Neshchadim, Sergey

N1 - Funding Information: Acknowledgments. The study presented was supported by the Russian Academy of Science (the Program of basic research), project FWNF-2022-0015. Publisher Copyright: © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2022

Y1 - 2022

N2 - In this paper we consider three problems of searching for disjoint subsets among a finite set of points in an Euclidean space. In all three problems, it is required to maximize the size of the minimal cluster so that each intra-cluster scatter of points relative to the cluster center does not exceed a predetermined threshold. In the first problem, the centers of the clusters are given as input. In the second problem, the centers are unknown, but belong to the initial set. In the last problem, the center of each cluster is defined as the arithmetic mean of all its elements. It is known that all three problems are NP-hard even in the one-dimensional case. The main result of the work is constant-factor approximation algorithms for all three problems. For the first two problems, 1/2-approximate algorithms for an arbitrary space dimension are constructed. Also we propose a 1/2-approximate algorithm for the one-dimensional case of the third problem.

AB - In this paper we consider three problems of searching for disjoint subsets among a finite set of points in an Euclidean space. In all three problems, it is required to maximize the size of the minimal cluster so that each intra-cluster scatter of points relative to the cluster center does not exceed a predetermined threshold. In the first problem, the centers of the clusters are given as input. In the second problem, the centers are unknown, but belong to the initial set. In the last problem, the center of each cluster is defined as the arithmetic mean of all its elements. It is known that all three problems are NP-hard even in the one-dimensional case. The main result of the work is constant-factor approximation algorithms for all three problems. For the first two problems, 1/2-approximate algorithms for an arbitrary space dimension are constructed. Also we propose a 1/2-approximate algorithm for the one-dimensional case of the third problem.

KW - Approximation algorithm

KW - Bounded scatter

KW - Clustering

KW - Euclidean space

KW - Max-min problem

KW - NP-hardness

UR - http://www.scopus.com/inward/record.url?scp=85140483507&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/a43947ea-eda5-36f4-b505-0056bb84e17a/

U2 - 10.1007/978-3-031-16224-4_6

DO - 10.1007/978-3-031-16224-4_6

M3 - Conference contribution

AN - SCOPUS:85140483507

SN - 9783031162237

T3 - Communications in Computer and Information Science

SP - 89

EP - 103

BT - Mathematical Optimization Theory and Operations Research

A2 - Kochetov, Yury

A2 - Eremeev, Anton

A2 - Khamisov, Oleg

A2 - Rettieva, Anna

PB - Springer Science and Business Media Deutschland GmbH

T2 - 21st International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2022

Y2 - 2 July 2022 through 6 July 2022

ER -

ID: 38414993