Approximation Scheme for a Sequence Weighted 2-Clustering with a Fixed Center of One Cluster Научная публикация
| Конференция |
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 июн. - 6 июл. 2024 , Омск |
||
|---|---|---|---|
| Сборник | Mathematical Optimization Theory and Operations Research: Recent Trends Сборник, Springer. 2024. 388 c. ISBN 978-3-031-73364-2. |
||
| Журнал |
Communications in Computer and Information Science
ISSN: 1865-0929 |
||
| Вых. Данные | Год: 2024, Том: 2239, Страницы: 349–360 Страниц : 12 DOI: 10.1007/978-3-031-73365-9_24 | ||
| Ключевые слова | Euclidean space, Weighted 2-clustering, Quadratic variation, NP-hardness, Approximation algorithm, FPTAS, Sequence clustering problem | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0015 |
Реферат:
We consider a problem of 2-clustering of a finite sequence of points in Euclidean space. In this problem, we need to partition an input sequence into two subsequences (clusters) minimizing weighted intracluster sums of the squared distances from clusters elements to their centers. The center of the first cluster is its centroid, while the center of the second one is the origin. Some constants are used to define the boundaries of the difference between any two subsequent indices of the elements in the cluster with an unknown centroid. The problem is a generalization of previously considered problems with specific weights, as it includes the input for the weight factors for both intracluster sums. In the paper, we present an approximation algorithm. It is based on an adaptive-grid approach and dynamic programming. If the dimension of the space is fixed, this algorithm constitutes an FPTAS.
Библиографическая ссылка:
Panasenko A.
Approximation Scheme for a Sequence Weighted 2-Clustering with a Fixed Center of One Cluster
В сборнике Mathematical Optimization Theory and Operations Research: Recent Trends. – Springer., 2024. – Т.2239. – C.349–360. – ISBN 978-3-031-73364-2. DOI: 10.1007/978-3-031-73365-9_24 Scopus OpenAlex
Approximation Scheme for a Sequence Weighted 2-Clustering with a Fixed Center of One Cluster
В сборнике Mathematical Optimization Theory and Operations Research: Recent Trends. – Springer., 2024. – Т.2239. – C.349–360. – ISBN 978-3-031-73364-2. DOI: 10.1007/978-3-031-73365-9_24 Scopus OpenAlex
Даты:
| Опубликована online: | 20 дек. 2024 г. |
| Опубликована в печати: | 16 янв. 2025 г. |
Идентификаторы БД:
| Scopus: | 2-s2.0-85214203492 |
| OpenAlex: | W4405599321 |
Цитирование в БД:
Пока нет цитирований