RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2014 Volume 21, Issue 1, Pages 53–66 (Mi da760)

This article is cited in 13 papers

Approximation algorithm for one problem of partitioning a sequence

A. V. Kelmanovab, S. A. Khamidullinb

a Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia
b Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia

Abstract: We consider one NP-hard problem of partitioning of a finite Euclidean vectors sequence into two clusters minimizing the sum of squared distances from the clusters elements to their centers. The cardinalities of the clusters are fixed. The center of the first cluster is defined as the mean value of all vectors in a cluster. The center of the second cluster is given in advance and is equal to 0. Additionally, the partition must satisfy the restriction that for all vectors that are in the first cluster the difference between the indices of two consequent vectors from this cluster is bounded from below and above by some constants. An effective $2$-approximation algorithm for the problem is presented. Bibliogr. 9.

Keywords: Euclidean vectors sequence, ñlusterization, minimum sum-of-squared distances, NP-hardness, effective $2$-approximation algorithm.

UDC: 519.16+519.85

Received: 01.03.2013
Revised: 13.05.2013


 English version:
Journal of Applied and Industrial Mathematics, 2014, 8:2, 236–244

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024