Exact pseudopolynomial algorithm for one sequence partitioning problem

详细信息    查看全文

• 作者：A. V. Kel’manov ; S. A. Khamidullin ; V. I. Khandeev
• 关键词：Key wordspartition ; sequence of vectors ; Euclidean space ; minimal sum of squared distances ; NP ; hardness ; exact pseudopolynomial algorithm
• 刊名：Automation and Remote Control
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：78
• 期：1
• 页码：67-74
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Systems Theory, Control; Control, Robotics, Mechatronics; Mechanical Engineering; Computer-Aided Engineering (CAD, CAE) and Design;
• 出版者：Pleiades Publishing
• ISSN：1608-3032
• 卷排序：78

文摘

We consider a strongly NP-hard problem of partitioning a finite sequence of vectors in a Euclidean space into two clusters of given size with the criterion of minimizing the total sum of square distances from cluster elements to their centers. The center of the first cluster is subject to optimization, defined by the mean value of all vectors in this cluster. The center of the second cluster is fixed at the origin. The partition is subject to the following condition: the difference between indices of two subsequent vectors included in the first cluster is bounded from above and below by given constants. We propose an exact pseudopolynomial algorithm for the case of a problem where the dimension of the space is fixed, and components of input vectors are integer-valued.