Skip to main content
Springer Nature Link
Log in

On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line

  • Conference paper
  • First Online:
Learning and Intelligent Optimization (LION 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11968))

Included in the following conference series:

  • 776 Accesses

Abstract

We consider one problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum over all clusters of the intracluster sums of the squared distances between clusters elements and their centers. The centers of some clusters are given as an input, while the other centers are unknown and defined as centroids (geometrical centers). It is known that the general case of the problem is strongly NP-hard. We show that there exists an exact polynomial algorithm for the one-dimensional case of the problem.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
CHF34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
CHF 24.95
Price includes VAT (Switzerland)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
CHF 47.00
Price excludes VAT (Switzerland)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
CHF 59.00
Price excludes VAT (Switzerland)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Fisher, R.A.: Statistical Methods and Scientific Inference. Hafner, New York (1956)

    MATH  Google Scholar 

  2. MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297. University of California Press, Berkeley (1967)

    Google Scholar 

  3. Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245–248 (2009)

    Article  Google Scholar 

  4. Rao, M.: Cluster analysis and mathematical programming. J. Am. Stat. Assoc. 66, 622–626 (1971)

    Article  Google Scholar 

  5. Bellman, R.: Dynamic Programming. Princeton University Press, Princeton (1957)

    MATH  Google Scholar 

  6. Glebov, N.I.: On the convex sequences. Discrete Anal. 4, 10–22 (1965). in Russian

    MathSciNet  Google Scholar 

  7. Gimadutdinov, E.K.: On the properties of solutions of one location problem of points on a segment. Control. Syst. 2, 77–91 (1969). in Russian

    MathSciNet  Google Scholar 

  8. Gimadutdinov, E.K.: On one class of nonlinear programming problems. Control. Syst. 3, 101–113 (1969). in Russian

    Google Scholar 

  9. Gimadi (Gimadutdinov) E.Kh.: The choice of optimal scales in one class of location, unification and standardization problems. Control. Syst. 6, 57–70 (1970). in Russian

    Google Scholar 

  10. Wu, X.: Optimal quantization by matrix searching. J. Algorithms 12(4), 663–673 (1991)

    Article  MathSciNet  Google Scholar 

  11. Grønlund, A., Larsen, K.G., Mathiasen, A., Nielsen, J.S., Schneider, S., Song, M.: Fast exact \(k\)-means, \(k\)-medians and Bregman divergence clustering in 1D. CoRR arXiv:1701.07204 (2017)

  12. Kel’manov, A.V., Khamidullin, S.A., Kel’manova, M.A.: Joint finding and evaluation of a repeating fragment in noised number sequence with given number of quasiperiodic repetitions. In: Book of Abstract of the Russian Conference “Discrete Analysis and Operations Research” (DAOR-4), p. 185. Sobolev Institute of Mathematics SB RAN, Novosibirsk (2004)

    Google Scholar 

  13. Gimadi, E.K., Kel’manov, A.V., Kel’manova, M.A., Khamidullin, S.A.: A posteriori detection of a quasi periodic fragment in numerical sequences with given number of recurrences. Sib. J. Ind. Math. 9(1(25)), 55–74 (2006). in Russian

    MATH  Google Scholar 

  14. 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)

    Article  Google Scholar 

  15. Kel’manov, A.V., Khamidullin, S.A.: Posterior detection of a given number of identical subsequences in a guasi-periodic sequence. Comput. Math. Math. Phys. 41(5), 762–774 (2001)

    MathSciNet  MATH  Google Scholar 

  16. 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)

    Article  MathSciNet  Google Scholar 

  17. 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)

    Article  Google Scholar 

  18. Kel’manov, A.V., Pyatkin, A.V.: On the complexity of a search for a subset of “similar” vectors. Dokl. Math. 78(1), 574–575 (2008)

    Article  MathSciNet  Google Scholar 

  19. Kel’manov, A.V., Pyatkin, A.V.: On a version of the problem of choosing a vector subset. J. Appl. Ind. Math. 3(4), 447–455 (2009)

    Article  MathSciNet  Google Scholar 

  20. 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)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

The study presented in Sects. 3 and 4 was supported by the Russian Foundation for Basic Research, projects 19-01-00308 and 18-31-00398. The study presented in the other sections was supported by the Russian Academy of Science (the Program of basic research), project 0314-2019-0015, and by the Russian Ministry of Science and Education under the 5-100 Excellence Programme.

Author information

Authors and Affiliations

  1. Sobolev Institute of Mathematics, 4 Koptyug Ave., 630090, Novosibirsk, Russia

    Alexander Kel’manov & Vladimir Khandeev

  2. Novosibirsk State University, 2 Pirogova St., 630090, Novosibirsk, Russia

    Alexander Kel’manov & Vladimir Khandeev

Authors
  1. Alexander Kel’manov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vladimir Khandeev
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vladimir Khandeev .

Editor information

Editors and Affiliations

  1. Technical University of Crete, Chania, Greece

    Nikolaos F. Matsatsinis

  2. Technical University of Crete, Chania, Greece

    Yannis Marinakis

  3. Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA

    Panos Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kel’manov, A., Khandeev, V. (2020). On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. In: Matsatsinis, N., Marinakis, Y., Pardalos, P. (eds) Learning and Intelligent Optimization. LION 2019. Lecture Notes in Computer Science(), vol 11968. Springer, Cham. https://doi.org/10.1007/978-3-030-38629-0_4

Download citation

Publish with us

Policies and ethics

Search

Navigation

  NODES
Idea 8
idea 8
INTERN 1
Note 2
Project 2