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:
Critical and Maximum Independent Sets Revisited Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Maximum Diversity Problem with Squared Euclidean Distance

Authors : Anton V. Eremeev, Alexander V. Kel’manov, Mikhail Y. Kovalyov, Artem V. Pyatkin

Published in: Mathematical Optimization Theory and Operations Research

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

In this paper we consider the following Maximum Diversity Subset problem. Given a set of points in Euclidean space, find a subset of size M maximizing the squared Euclidean distances between the chosen points. We propose an exact dynamic programming algorithm for the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, the algorithm has a pseudo-polynomial time complexity. Using this algorithm, we develop an FPTAS for the special case where the dimension of the Euclidean space is bounded by a constant. We also propose a new proof of strong NP-hardness of the problem in the general case.

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 Semi-supervised Classification Using Multiple Clustering and Low-Rank Matrix Operations
next chapter Estimation of the Necessary Sample Size for Approximation of Stochastic Optimization Problems with Probabilistic Criteria
Literature
1.
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
2.
3.
Cevallos, A., Eisenbrand, F., Morell, S.: Diversity maximization in doubling metrics. In: Proceedings of 29th International Symposium on Algorithms and Computation (ISAAC 2018). LIPIcs, vol. 123, pp. 33:1–33:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2016). https://​doi.​org/​10.​4230/​LIPIcs.​ISAAC.​2018.​33
4.
5.
Edwards, A.W.F., Cavalli-Sforza, L.L.: A method for cluster analysis. Biometrics 21, 362–375 (1965)CrossRef
6.
Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco (1979)MATH
7.
Ibarra, O., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463–468 (1975)MathSciNetCrossRef
8.
9.
Kel’manov, A.V., Pyatkin, A.V.: NP-completeness of some problems of choosing a vector subset. J. Appl. Ind. Math. 5(3), 352–357 (2011)MathSciNetCrossRef
10.
Kel’manov, A.V., Romanchenko, S.M.: Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems. Autom. Remote Control 73(2), 349–354 (2012)MathSciNetCrossRef
11.
Kel’manov, A.V., Romanchenko, S.M.: An approximation algorithm for solving a problem of search for a vector subset. J. Appl. Ind. Math. 6(1), 90–96 (2012)MathSciNetCrossRef
12.
Kel’manov, A.V., Romanchenko, S.M.: An FPTAS for a vector subset search problem. J. Appl. Ind. Math. 8(3), 329–336 (2014)MathSciNetCrossRef
13.
14.
Kuo, C.C., Glover, F., Dhir, K.S.: Analyzing and modeling the maximum diversity problem by zero-one programming. Decis. Sci. 24(6), 1171–1185 (1993)CrossRef
15.
McConnell, S.: The new battle over immigration. Fortune 117(10), 89–102 (1988)
16.
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, New York (1994)MATH
17.
Porter, W.M., Eawal, K.M., Rachie, K.O., Wien, H.C., Willians, R.C.: Cowpea germplasm catalog No. 1. International Institute of Tropical Agriculture, Ibadan, Nigeria (1975)
18.
Shenmaier, V.V.: An approximation scheme for a problem of search for a vector subset. J. Appl. Ind. Math. 6(3), 381–386 (2012)MathSciNetCrossRef
19.
Shenmaier, V.V.: Solving some vector subset problems by Voronoi diagrams. J. Appl. Ind. Math. 10(4), 560–566 (2016)MathSciNetCrossRef
Metadata
Title
Maximum Diversity Problem with Squared Euclidean Distance
Authors
Anton V. Eremeev
Alexander V. Kel’manov
Mikhail Y. Kovalyov
Artem V. Pyatkin
Copyright Year
2019
Book
Mathematical Optimization Theory and Operations Research

Print ISBN: 978-3-030-22628-2

Electronic ISBN: 978-3-030-22629-9

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-22629-9_38

Premium Partner

    Image Credits