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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

On the Complexity of Some Quadratic Euclidean Partition Problems into Balanced Clusters

verfasst von : Alexander Kel’manov, Vladimir Khandeev, Artem Pyatkin

Erschienen in: Optimization and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We consider three problems of partitioning a finite set of N points in the d-dimensional Euclidean space into two clusters balancing the value of (1) the normalized by a cluster size sum of squared deviations from the mean, (2) the sum of squared deviations from the mean, and (3) the size-weighted sum of squared deviations from the mean. We have proved the NP-completeness of all these problems.

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 On Optimization Problem Arising in Computer Simulation of Crystal Structures
Nächstes Kapitel An Approximate Solution of a GNSS Satellite Selection Problem Using Semidefinite Programming
Literatur
1.
2.
3.
Han, J., Kamber, M., Pei, J.: Data Mining: Concepts and Techniques, 3rd edn. Morgan Kaufmann, Burlington (2012)MATH
4.
Shirkhorshidi, A.S., Aghabozorgi, S., Wah, T.Y., Herawan, T.: Big data clustering: a review. LNCS 8583, 707–720 (2014)
5.
Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245–248 (2009)CrossRef
6.
Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. Theor. Comput. Sci. 442, 13–21 (2012)MathSciNetCrossRef
7.
Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 106–113 (1998)
8.
Papadimitriou, C.H.: Worst-case and probabilistic analysis of a geometric location problem. SIAM J. Comput. 10(3), 542–557 (1981)MathSciNetCrossRef
9.
Masuyama, S., Ibaraki, T., Hasegawa, T.: The computational complexity of the m-center problems in the plane. IEEE Trans. IECE Jpn 64(2), 57–64 (1981)
10.
Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the k-center problem. Math. Oper. Res. 10(2), 180–184 (1985)MathSciNetCrossRef
11.
Aggarwal, H., Imai, N., Katoh, N., Suri, S.: Finding \(k\) points with minimum diameter and related problems. J. Algorithms 12(1), 38–56 (1991)MathSciNetCrossRef
12.
13.
Indyk, P.: A sublinear time approximation scheme for clustering in metric space. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 154–159 (1999)
14.
Hansen, P., Jaumard, B., Mladenovich, N.: Minimum sum of squares clustering in a low dimensional space. J. Classification 15, 37–55 (1998)MathSciNetCrossRef
15.
Hansen, P., Jaumard, B.: Cluster analysis and mathematical programming. Math. Programm. 79, 191–215 (1997)MathSciNetMATH
16.
Snedecor, G.W., Cochran, W.G.: Statistical Methods, 8th edn. Iowa State University Press, Iowa (1989)MATH
17.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)MATH
Metadaten
Titel
On the Complexity of Some Quadratic Euclidean Partition Problems into Balanced Clusters
verfasst von
Alexander Kel’manov
Vladimir Khandeev
Artem Pyatkin
Copyright-Jahr
2020
Buch
Optimization and Applications

Print ISBN: 978-3-030-38602-3

Electronic ISBN: 978-3-030-38603-0

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-38603-0_10