Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






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


Diskretnyi Analiz i Issledovanie Operatsii, 2014, Volume 21, Issue 1, Pages 53–66 (Mi da760)  

This article is cited in 13 scientific papers (total 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
References:
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.
Received: 01.03.2013
Revised: 13.05.2013
English version:
Journal of Applied and Industrial Mathematics, 2014, Volume 8, Issue 2, Pages 236–244
DOI: https://doi.org/10.1134/S1990478914020100
Bibliographic databases:
Document Type: Article
UDC: 519.16+519.85
Language: Russian
Citation: A. V. Kelmanov, S. A. Khamidullin, “Approximation algorithm for one problem of partitioning a sequence”, Diskretn. Anal. Issled. Oper., 21:1 (2014), 53–66; J. Appl. Industr. Math., 8:2 (2014), 236–244
Citation in format AMSBIB
\Bibitem{KelKha14}
\by A.~V.~Kelmanov, S.~A.~Khamidullin
\paper Approximation algorithm for one problem of partitioning a~sequence
\jour Diskretn. Anal. Issled. Oper.
\yr 2014
\vol 21
\issue 1
\pages 53--66
\mathnet{http://mi.mathnet.ru/da760}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3288381}
\transl
\jour J. Appl. Industr. Math.
\yr 2014
\vol 8
\issue 2
\pages 236--244
\crossref{https://doi.org/10.1134/S1990478914020100}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84902178105}
Linking options:
  • https://www.mathnet.ru/eng/da760
  • https://www.mathnet.ru/eng/da/v21/i1/p53
  • This publication is cited in the following 13 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Statistics & downloads:
    Abstract page:407
    Full-text PDF :90
    References:74
    First page:20
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024