RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Trudy Inst. Mat. i Mekh. UrO RAN, 2016, Volume 22, Number 3, Pages 144–152 (Mi timm1329)  

An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities

A. V. Kel'manovab, L. V. Mikhailovaa, S. A. Khamidullina, V. I. Khandeeva

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University

Abstract: We consider the problem of partitioning a finite sequence of points in Euclidean space into a given number of clusters (subsequences) minimizing the sum over all clusters of intracluster sums of squared distances from elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is specified at the origin, while the centers of the other clusters are unknown. Very unknown cluster center is defined as the mean value of cluster elements. Additionally, there are a few structural constraints on the elements of the sequence that enter the clusters with unknown centers: (1) the concatenation of indices of elements of these clusters is an increasing sequence, (2) the difference between two consequent indices is bounded from below and above by prescribed constants, and (3) the total number of elements in these clusters is given as an input. It is shown that the problem is strongly NP-hard. A 2-approximation algorithm that is polynomial for a fixed number of clusters is proposed for this problem.

Keywords: partitioning, sequence, Euclidean space, minimum sum of squared distances, NP-hardness, approximation algorithm.

Funding Agency Grant Number
Russian Science Foundation 16-11-10041


DOI: https://doi.org/10.21538/0134-4889-2016-22-3-144-152

Full text: PDF file (182 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2017, 299, suppl. 1, 88–96

Bibliographic databases:

UDC: 519.16 + 519.85
MSC: 68W25, 68Q25
Received: 30.05.2016

Citation: A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities”, Trudy Inst. Mat. i Mekh. UrO RAN, 22, no. 3, 2016, 144–152; Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96

Citation in format AMSBIB
\Bibitem{KelMikKha16}
\by A.~V.~Kel'manov, L.~V.~Mikhailova, S.~A.~Khamidullin, V.~I.~Khandeev
\paper An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2016
\vol 22
\issue 3
\pages 144--152
\mathnet{http://mi.mathnet.ru/timm1329}
\crossref{https://doi.org/10.21538/0134-4889-2016-22-3-144-152}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3555718}
\elib{http://elibrary.ru/item.asp?id=26530887}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2017
\vol 299
\issue , suppl. 1
\pages 88--96
\crossref{https://doi.org/10.1134/S0081543817090115}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000425144600010}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85042147861}


Linking options:
  • http://mi.mathnet.ru/eng/timm1329
  • http://mi.mathnet.ru/eng/timm/v22/i3/p144

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Number of views:
    This page:168
    Full text:30
    References:24
    First page:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020