|
Avtomatika i Telemekhanika, 2014, Issue 4, Pages 5–19
(Mi at7528)
|
|
|
|
This article is cited in 11 scientific papers (total in 11 papers)
Mathematical programming problems
A $2$-approximate algorithm to solve one problem of the family of disjoint vector subsets
A. E. Galashova, A. V. Kel'manovb a Novosibirsk State University, Novosibirsk, Russia
b Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
Abstract:
Consideration was given to the problem of seeking a family of disjoint subsets of given cardinalities in a finite set of Euclidean space vectors. The minimal sum of the squared distances from the subset elements to their centers was used as the search criterion. The subset centers are optimizable variables defined as the mean values over the elements of the required subsets. The problem was shown to be NP-hard in the strong sense. To solve it, a $2$-approximate algorithm was proposed which is polynomial for a fixed number of the desired subsets.
Citation:
A. E. Galashov, A. V. Kel'manov, “A $2$-approximate algorithm to solve one problem of the family of disjoint vector subsets”, Avtomat. i Telemekh., 2014, no. 4, 5–19; Autom. Remote Control, 75:4 (2014), 595–606
Linking options:
https://www.mathnet.ru/eng/at7528 https://www.mathnet.ru/eng/at/y2014/i4/p5
|
Statistics & downloads: |
Abstract page: | 346 | Full-text PDF : | 55 | References: | 85 | First page: | 36 |
|