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
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Journal of Applied and Industrial Mathematics
Erschienen in: Journal of Applied and Industrial Mathematics 2/2020

01.05.2020

Computational Complexity of the Problem of Choosing Typical Representatives in a \(\boldsymbol 2\) -Clustering of a Finite Set of Points in a Metric Space

verfasst von: I. A. Borisova

Erschienen in: Journal of Applied and Industrial Mathematics | Ausgabe 2/2020

Einloggen

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

search-config
loading …

Abstract

We consider the computational complexity of one extremal problem of choosing a subset of \(p \) points from some given \(2 \)-clustering of a finite set in a metric space. The chosen subset of points has to describe the given clusters in the best way from the viewpoint of some geometric criterion. This is a formalization of an applied problem of data mining which consists in finding a subset of typical representatives of a dataset composed of two classes based on the function of rival similarity. The problem is proved to be NP-hard. To this end, we polynomially reduce to the problem one of the well-known problems NP-hard in the strong sense, the \(p \)-median problem.
Vorheriger Artikel Simulation of the Stationary Nonisothermal MHD Flows of Polymeric Fluids in Channels with Interior Heating Elements
Nächster Artikel Mathematical and Numerical Models of the Central Regulatory Circuit of the Morphogenesis System of Drosophila

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
Literatur
1.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).MATH
2.
D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-Hardness of Euclidean Sum-of-Squares Clustering,” Machine Learning 75 (2), 245–248 (2009).CrossRef
3.
S. Dasgupta, “The Hardness of \(k \)-Means Clustering,” in Technical Report CS2007-0890 (University of California, San Diego, 2008), pp. 1–6.
4.
C. H. Papadimitriou, “Worst-Case and Probabilistic Analysis of a Geometric Location Problem,” SIAM J. Comput. 10 (3), 542–557 (1981).MathSciNetCrossRef
5.
S. Har-Peled and S. Mazumdar, “Coresets for \(k \)-Means and \(k \)-Median Clustering and Their Applications,” inProceedings of 36th Annual ACM Symposium on Theory of Computing (Chicago, Illinois, USA, June 13-15, 2004), pp. 291–300.
6.
L. Kaufman and P. J. Rousseeuw, “Clustering by Means of Medoids,” inStatistical Data Analysis Based on the \(L_1 \)-Norm and Related Methods, Ed. by Y. Dodge (North Holland, Amsterdam, 1987), pp. 405–416.
7.
A. V. Kel’manov, A. V. Pyatkin, and V. I. Khandeev, “Complexity of Some Max-Min Clustering Problems,” Trudy Inst. Mat. Mekh. Ural. Otdel. Ross. Akad. Nauk24 (4), 189–198 (2018).MathSciNet
8.
A. V. Kel’manov and A. V. Pyatkin, “NP-Hardness of Some Euclidean Problems of Partition of a Finite Point Set,” Zh. Vychisl. Mat. Mat. Fiz. 58 (5), 852–856 (2018).MATH
9.
H. Aggarwal, N. Imai, N. Katoh, and S. Suri, “Finding \(k \) Points with Minimum Diameter and Related Problems,” J. Algorithms 12 (1), 38–56 (1991).MathSciNetCrossRef
10.
S. Banerjee, S. Bhore, and R. Chitnis, “Algorithms and Hardness Results for Nearest Neighbor Problems in Bicolored Point Sets,” in Proceedings of the 13th Latin American Theoretical Informatics Symposium (LATIN) (Buenos Aires, Argentina, April 16-19, 2018), pp. 80–93.
11.
A. V. Zukhba, “NP-Completeness of the Problem of Prototype Selection in the Nearest Neighbor Method,” Pattern Recognition and Image Analysis 20 (4), 484–494 (2010).CrossRef
12.
V. N. Vapnik, The Reconstruction of Dependencies from Empirical Data (Nauka, Moscow, 1974) [in Russian].
13.
C. J. C. Burges, “A Tutorial on Support Vector Machines for Pattern Recognition,” Data Mining Knowl. Discov. 2 (2), 121–167 (1998).CrossRef
14.
N. G. Zagoruiko, I. A. Borisova, V. V. Dyubanov, and O. A. Kutnenko, “Methods of Recognition Based on the Function of Rival Similarity,” Pattern Recognition and Image Analysis 18 (1), 1–6 (2008).CrossRef
15.
O. Kariv and S. Hakimi, “An Algorithmic Approach to Network Location Problems. The p-Medians,” SIAM J. Appl. Math. 37, 539–560 (1979).MathSciNetCrossRef
Metadaten
Titel
Computational Complexity of the Problem of Choosing Typical Representatives in a -Clustering of a Finite Set of Points in a Metric Space
verfasst von
I. A. Borisova
Publikationsdatum
01.05.2020
Verlag
Pleiades Publishing
Erschienen in
Journal of Applied and Industrial Mathematics / Ausgabe 2/2020
Print ISSN: 1990-4789
Elektronische ISSN: 1990-4797
DOI
https://doi.org/10.1134/S1990478920020039

Weitere Artikel der Ausgabe 2/2020

Journal of Applied and Industrial Mathematics 2/2020 Zur Ausgabe

OriginalPaper

Reconstruction of the Lambert Curve in a Scattering Medium by Using Pulsed Sounding

OriginalPaper

Numerical Study of Nonlinear Oscillations in a Clock Frequency MEMS-Generator

OriginalPaper

Analysis of an Epidemic Mathematical Model Based on Delay Differential Equations

OriginalPaper

The Problem of Determining the 2D Kernel in a System of Integro-Differential Equations of a Viscoelastic Porous Medium

OriginalPaper

Raising the Accuracy of Monitoring the Optical Coating Deposition by Application of a Nonlocal Algorithm of Data Analysis

OriginalPaper

Mathematical and Numerical Models of the Central Regulatory Circuit of the Morphogenesis System of Drosophila

Premium Partner

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen. 

    Zur Marktübersicht
    Bildnachweise