Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Automated Detection of Adverse Drug Reactions from Social Media Posts with Machine Learning Read chapter Read first chapter

2018 | OriginalPaper | Chapter

A Randomized Algorithm for 2-Partition of a Sequence

Authors : Alexander Kel’manov, Sergey Khamidullin, Vladimir Khandeev

Published in: Analysis of Images, Social Networks and Texts

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the paper we consider one strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters minimizing the sum over both clusters of intracluster sum of squared distances from clusters elements to their centers. The cardinalities of clusters are assumed to be given. The center of the first cluster is unknown and is defined as the mean value of all points in the cluster. The center of the second one is the origin. Additionally, the difference between the indexes of two consequent points from the first cluster is bounded from below and above by some constants. A randomized algorithm for the problem is proposed. For an established parameter value, given a relative error \(\varepsilon > 0\) and fixed \(\gamma \in (0, 1)\), this algorithm allows to find a \((1 + \varepsilon )\)-approximate solution of the problem with a probability of at least \(1 - \gamma \) in polynomial time. The conditions are established under which the algorithm is polynomial and asymptotically exact.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Approximation Algorithms for the Maximum m-Peripatetic Salesman Problem
next chapter An Approximation Scheme for a Weighted Two-Cluster Partition Problem
Literature
1.
Fu, T.: A review on time series data mining. Eng. Appl. Artif. Intell. 24(1), 164–181 (2011)CrossRef
2.
3.
Liao, T.W.: Clustering of time series data – a survey. Pattern Recogn. 38(11), 1857–1874 (2005)CrossRefMATH
4.
5.
Carter, J.A., Agol, E., et al.: Kepler-36: a pair of planets with neighboring orbits and dissimilar densities. Science 337(6094), 556–559 (2012)CrossRef
6.
Kel’manov, A.V., Jeon, B.: A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train. IEEE Trans. Sig. Process. 52(3), 645–656 (2004)MathSciNetCrossRefMATH
7.
Rajeev, M., Prabhakar, R.: Randomized Algorithms. Cambridge University Press, New York (1995)MATH
8.
Kel’manov, A.V., Pyatkin, A.V.: On complexity of some problems of cluster analysis of vector sequences. J. Appl. Ind. Math. 7(3), 363–369 (2013)MathSciNetCrossRefMATH
9.
Kel’manov, A.V., Khamidullin, S.A.: An approximating polynomial algorithm for a sequence partitioning problem. J. Appl. Ind. Math. 8(2), 236–244 (2014)MathSciNetCrossRefMATH
10.
Kel’manov, A.V., Khamidullin, S.A., Khandeev, V.I.: Exact pseudopolynomial algorithm for one sequence partitioning problem. Autom. Remote Control 78(1), 67–74 (2017)MathSciNetCrossRefMATH
11.
Kel’manov, A.V., Khamidullin, S.A., Khandeev, V.I.: A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem. J. Appl. Ind. Math. 10(2), 209–219 (2016)MathSciNetCrossRefMATH
12.
Gimadi, E.K., Kel’manov, A.V., Kel’manova, M.A., Khamidullin, S.A.: A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence (in Russian). Sibirsk. Zh. Ind. Mat. 9(1), 55–74 (2006)MATH
13.
Gimadi, E.K., Kel’manov, A.V., Kel’manova, M.A., Khamidullin, S.A.: A posteriori detecting a quasiperiodic fragment in a numerical sequence. Pattern Recogn. Image Anal. 18(1), 30–42 (2008)CrossRefMATH
14.
Kel’manov, A.V.: Off-line detection of a quasi-periodically recurring fragment in a numerical sequence. Proc. Steklov Inst. Math. 263(S2), 84–92 (2008)MathSciNetCrossRefMATH
15.
Kel’manov, A.V., Pyatkin, A.V.: Complexity of certain problems of searching for subsets of vectors and cluster analysis. Comput. Math. Math. Phys. 49(11), 1966–1971 (2009)MathSciNetCrossRefMATH
16.
Kel’manov, A.V., Khandeev, V.I.: Fully polynomial-time approximation scheme for a special case of a quadratic euclidean 2-clustering problem. Comput. Math. Math. Phys. 56(2), 334–341 (2016)MathSciNetCrossRefMATH
17.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)MATH
18.
Kel’manov, A.V., Khandeev, V.I.: A randomized algorithm for two-cluster partition of a set of vectors. Comput. Math. Math. Phys. 55(2), 330–339 (2015)MathSciNetCrossRefMATH
19.
Kel’manov, A.V., Khamidullin, S.A.: Posterior detection of a given number of identical subsequences in a quasi-periodic sequence. Comput. Math. Math. Phys. 41(5), 762–774 (2001)MathSciNetMATH
Metadata
Title
A Randomized Algorithm for 2-Partition of a Sequence
Authors
Alexander Kel’manov
Sergey Khamidullin
Vladimir Khandeev
Copyright Year
2018
Book
Analysis of Images, Social Networks and Texts

Print ISBN: 978-3-319-73012-7

Electronic ISBN: 978-3-319-73013-4

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-73013-4_29

Premium Partner

    Image Credits