Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Automated Detection of Adverse Drug Reactions from Social Media Posts with Machine Learning Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

A Randomized Algorithm for 2-Partition of a Sequence

verfasst von : Alexander Kel’manov, Sergey Khamidullin, Vladimir Khandeev

Erschienen in: Analysis of Images, Social Networks and Texts

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Approximation Algorithms for the Maximum m-Peripatetic Salesman Problem
Nächstes Kapitel An Approximation Scheme for a Weighted Two-Cluster Partition Problem
Literatur
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
Metadaten
Titel
A Randomized Algorithm for 2-Partition of a Sequence
verfasst von
Alexander Kel’manov
Sergey Khamidullin
Vladimir Khandeev
Copyright-Jahr
2018
Buch
Analysis of Images, Social Networks and Texts

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

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

Copyright-Jahr: 2018

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

Premium Partner

    Bildnachweise