Diskretnyi Analiz i Issledovanie Operatsii
General information
Latest issue
Impact factor
Guidelines for authors

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

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

This article is cited in 8 scientific papers (total in 8 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.

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

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

Bibliographic databases:

UDC: 519.16+519.85
Received: 01.03.2013
Revised: 13.05.2013

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
\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
\jour J. Appl. Industr. Math.
\yr 2014
\vol 8
\issue 2
\pages 236--244

Linking options:
  • http://mi.mathnet.ru/eng/da760
  • http://mi.mathnet.ru/eng/da/v21/i1/p53

    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

    This publication is cited in the following articles:
    1. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219  mathnet  crossref  crossref  mathscinet  elib
    2. 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”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96  mathnet  crossref  crossref  mathscinet  isi  elib
    3. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Exact pseudopolynomial algorithm for one sequence partitioning problem”, Autom. Remote Control, 78:1 (2017), 67–74  mathnet  crossref  isi  elib
    4. A. Kel'manov, “Efficient approximation algorithms for some NP-hard problems of partitioning a set and a sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 87–90  crossref  isi
    5. A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “A randomized algorithm for a sequence 2-clustering problem”, Comput. Math. Math. Phys., 58:12 (2018), 2078–2085  mathnet  crossref  crossref  isi  elib
    6. A. Kel'manov, S. Khamidullin, V. Khandeev, “A randomized algorithm for 2-partition of a sequence”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 313–322  crossref  mathscinet  isi  scopus
    7. Kel'manov A., Khamidullin S., Panasenko A., “Exact Algorithm For One Cardinality-Weighted 2-Partitioning Problem of a Sequence”, Learning and Intelligent Optimization, Lion, Lecture Notes in Computer Science, 11968, eds. Matsatsinis N., Marinakis Y., Pardalos P., Springer International Publishing Ag, 2020, 135–145  crossref  isi  scopus
    8. Kel'manov A. Khamidullin S. Panasenko A., “2-Approximation Polynomial-Time Algorithm For a Cardinality-Weighted 2-Partitioning Problem of a Sequence”, Numerical Computations: Theory and Algorithms, Pt II, Lecture Notes in Computer Science, 11974, ed. Sergeyev Y. Kvasov D., Springer International Publishing Ag, 2020, 386–393  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:304
    Full text:67
    First page:20

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021