Approximation Scheme for a Sequence Weighted 2-Clustering with a Fixed Center of One Cluster Full article
| Conference |
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 Jun - 6 Jul 2024 , Омск |
||
|---|---|---|---|
| Source | Mathematical Optimization Theory and Operations Research: Recent Trends Compilation, Springer. 2024. 388 c. ISBN 978-3-031-73364-2. |
||
| Journal |
Communications in Computer and Information Science
ISSN: 1865-0929 |
||
| Output data | Year: 2024, Volume: 2239, Pages: 349–360 Pages count : 12 DOI: 10.1007/978-3-031-73365-9_24 | ||
| Tags | Euclidean space, Weighted 2-clustering, Quadratic variation, NP-hardness, Approximation algorithm, FPTAS, Sequence clustering problem | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0015 |
Abstract:
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.
Cite:
Panasenko A.
Approximation Scheme for a Sequence Weighted 2-Clustering with a Fixed Center of One Cluster
In compilation 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
In compilation 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
Dates:
| Published online: | Dec 20, 2024 |
| Published print: | Jan 16, 2025 |
Identifiers:
| Scopus: | 2-s2.0-85214203492 |
| OpenAlex: | W4405599321 |
Citing:
Пока нет цитирований