### 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.

Original language | English |
---|---|

Title of host publication | Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers |

Editors | Nikolaos F. Matsatsinis, Yannis Marinakis, Panos Pardalos |

Publisher | Springer Gabler |

Pages | 46-52 |

Number of pages | 7 |

ISBN (Print) | 9783030386283 |

DOIs | |

Publication status | Published - 22 Jan 2020 |

Event | 13th International Conference on Learning and Intelligent Optimization, LION 13 - Chania, Greece Duration: 27 May 2019 → 31 May 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11968 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 13th International Conference on Learning and Intelligent Optimization, LION 13 |
---|---|

Country | Greece |

City | Chania |

Period | 27.05.2019 → 31.05.2019 |

### Keywords

- Euclidean space
- Minimum Sum-of-Squares Clustering
- NP-hard problem
- One-dimensional case
- Polynomial solvability

## Fingerprint Dive into the research topics of 'On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line'. Together they form a unique fingerprint.

## Cite this

Kel’manov, A., & Khandeev, V. (2020). On Polynomial Solvability of One Quadratic Euclidean Clustering Problem on a Line. In N. F. Matsatsinis, Y. Marinakis, & P. Pardalos (Eds.),

*Learning and Intelligent Optimization - 13th International Conference, LION 13, Revised Selected Papers*(pp. 46-52). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11968 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-38629-0_4