Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster

  • Published:
Proceedings of the Steklov Institute of Mathematics Aims and scope Submit manuscript

Abstract

We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The center of one cluster is unknown and is defined as the mean value of its elements (i.e., it is the centroid of the cluster). The center of the other cluster is fixed at the origin. The weight factors for the intracluster sums are given as input. We present an approximation algorithm for this problem, which is based on the adaptive grid approach to finding the center of the optimal cluster. We show that the algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of a fixed space dimension. If the dimension is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm implements a polynomial-time approximation scheme (PTAS).

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. V. Kel’manov and S. M. Romanchenko, “An FPTAS for a vector subset search problem,” J. Appl. Ind. Math. 8 (3), 329–336 (2014).

    Article  MathSciNet  MATH  Google Scholar 

  2. A. V. Kel’manov and V. I. Khandeev, “Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem,” Comp. Math. Math. Phys. 56 (2), 334–341 (2016).

    Article  MathSciNet  MATH  Google Scholar 

  3. A. V. Kel’manov and A. V. Motkova, “A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem,” in Discrete Optimization and Operations Research: Proceedings of the 9th International Conference, Vladivostok, Russia, 2016 (Springer, Cham, 2016), Ser. Lecture Notes in Computer Science 9869, pp. 182–192. doi 10.1007/978-3-319-44914-2 15

    MATH  Google Scholar 

  4. A. Aggarwal, H. Imai, N. Katoh, and S. Suri, “Finding k points with minimum diameter and related problems,” J. Algorithms 12 (1), 38–56 (1991). doi 10.1016/0196-6774(91)90022-Q

    Article  MathSciNet  MATH  Google Scholar 

  5. A. V. Kel’manov and A. V. Pyatkin, “NP-completeness of some problems of choosing a vector subset,” J. Appl. Ind. Math. 5 (3), 352–357 (2011).

    Article  MathSciNet  Google Scholar 

  6. V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams,” J. Appl. Ind. Math. 10 (4), 560–566 (2016).

    Article  MathSciNet  MATH  Google Scholar 

  7. A. V. Kel’manov and S. M. Romanchenko, “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems,” Autom. Remote Control 73 (2), 349–354 (2012).

    Article  MathSciNet  MATH  Google Scholar 

  8. A. V. Kel’manov and S. M. Romanchenko, “An approximation algorithm for solving a problem of search for a vector subset,” J. Appl. Ind. Math. 6 (1), 90–96 (2012).

    Article  MathSciNet  Google Scholar 

  9. V. V. Shenmaier, “An approximation scheme for a problem of search for a vector subset,” J. Appl. Ind. Math. 6 (3), 381–386 (2012).

    Article  MathSciNet  MATH  Google Scholar 

  10. E. Kh. Gimadi, A. V. Kel’manov, M. A. Kel’manova, and S. A. Khamidullin, “A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence,” Sib. Zh. Ind. Mat. 9 (1), 55–74 (2006).

    MathSciNet  MATH  Google Scholar 

  11. E. Kh. Gimadi, A. V. Kel’manov, M. A. Kel’manova, and S. A. Khamidullin, “A posteriori detecting a quasiperiodic fragment in a numerical sequence,” Pattern Recogn. Image Anal. 18 (1), 30–42 (2008). doi 10.1134/S1054661808010057

    Article  MATH  Google Scholar 

  12. A. V. Kel’manov and A. V. Pyatkin, “Complexity of certain problems of searching for subsets of vectors and cluster analysis,” Comp. Math. Math. Phys. 49 (11), 1966–1971 (2009).

    Article  MATH  Google Scholar 

  13. A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, and A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight,” J. Appl. Ind. Math. 2 (1), 32–38 (2008).

    Article  MathSciNet  MATH  Google Scholar 

  14. E. Kh. Gimadi, A. V. Pyatkin, and I. A. Rykov, “On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension,” J. Appl. Ind. Math. 4 (1), 48–53 (2010).

    Article  MathSciNet  Google Scholar 

  15. E. Kh. Gimadi, Yu. V. Glazkov, and I. A. Rykov, “On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in Euclidean space,” J. Appl. Ind. Math. 3 (3), 343–352 (2009).

    Article  MathSciNet  MATH  Google Scholar 

  16. A. V. Kel’manov and V. I. Khandeev, “An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors,” J. Appl. Ind. Math. 9 (4), 497–502 (2015).

    Article  MathSciNet  MATH  Google Scholar 

  17. A. V. Dolgushev and A. V. Kel’manov, “An approximation algorithm for solving a problem of cluster analysis,” J. Appl. Ind. Math. 5 (4), 551–558 (2011).

    Article  MathSciNet  MATH  Google Scholar 

  18. A. V. Dolgushev, A. V. Kel’manov, and V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters,” Proc. Steklov Inst. Math. 295 (Suppl. 1), S47–S56 (2016).

    Google Scholar 

  19. A. V. Kel’manov and V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors,” Comp. Math. Math. Phys. 55 (2), 330–339 (2015).

    Article  MathSciNet  MATH  Google Scholar 

  20. A. V. Kel’manov and A. V. Motkova, “Exact pseudopolynomial algorithms for a balanced 2-clustering problem,” J. Appl. Ind. Math. 10 (3), 349–355 (2016).

    Article  MathSciNet  MATH  Google Scholar 

  21. A. V. Kel’manov and A. V. Pyatkin, “NP-hardness of some quadratic Euclidean 2-clustering problems,” Dokl. Math. 92 (2), 634–637 (2015).

    Article  MathSciNet  MATH  Google Scholar 

  22. A. V. Kel’manov and A. V. Pyatkin, “On the complexity of some quadratic Euclidean 2-clustering problems,” Comp. Math. Math. Phys. 56 (3), 491–497 (2016).

    Article  MathSciNet  MATH  Google Scholar 

  23. C. C. Aggarwal, Data Mining: The Textbook (Springer, Cham, 2015).

    MATH  Google Scholar 

  24. C. M. Bishop, Pattern Recognition and Machine Learning (Springer, New York, 2006).

    MATH  Google Scholar 

  25. T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed. (Springer, New York, 2009).

    Book  MATH  Google Scholar 

  26. G. James, D. Witten, T. Hastie, and R. Tibshirani, An Introduction to Statistical Learning with Application in R (Springer, New York, 2013).

    Book  MATH  Google Scholar 

  27. A. K. Jain, “Data clustering: 50 years beyond k-means,” Pattern Recogn. Lett. 31 (8), 651–666 (2010). doi 10.1016/j.patrec.2009.09.011

    Article  Google Scholar 

  28. N. Wirth, Algorithms + Data Structures = Programs (Prentice Hall, Englewood Cliffs, NJ, 1976).

    MATH  Google Scholar 

  29. K. Ball, “An elementary introduction to modern convex geometry,” in Flavors of Geometry, Ed. by S. Levy (Cambridge Univ. Press, Cambridge, 1997), pp. 1–58.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090, Russia

    A. V. Kel’manov & V. V. Shenmaier

  2. Novosibirsk State University, Novosibirsk, 630090, Russia

    A. V. Kel’manov & A. V. Motkova

Authors
  1. A. V. Kel’manov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. V. Motkova
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. V. V. Shenmaier
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to A. V. Kel’manov, A. V. Motkova or V. V. Shenmaier.

Additional information

Original Russian Text © A.V. Kel’manov, A.V.Motkova, V.V. Shenmaier, 2017, published in Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2017, Vol. 23, No. 3, pp. 159–170.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kel’manov, A.V., Motkova, A.V. & Shenmaier, V.V. Approximation Scheme for the Problem of Weighted 2-Clustering with a Fixed Center of One Cluster. Proc. Steklov Inst. Math. 303 (Suppl 1), 136–145 (2018). https://doi.org/10.1134/S0081543818090146

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0081543818090146

Keywords

Search

Navigation