|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности
А. В. Кельмановab, С. А. Хамидуллинb, В. И. Хандеевb a Новосибирский государственный университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
b Институт математики им. С. Л. Соболева, пр. Коптюга, 4, 630090 Новосибирск, Россия
Аннотация:
Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности точек евклидова пространства на два кластера (подпоследовательности), имеющих заданные мощности, по критерию минимума суммы по обоим кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров неизвестен и определяется как среднее значение по всем элементам, образующим этот кластер, а центр второго задан в начале координат. При этом разбиение подчинено условию: разность между номерами последующего и предыдущего элементов последовательности, входящих в первый кластер, ограничена сверху и снизу заданными константами. Обоснована полностью полиномиальная приближённая схема для случая задачи, в котором размерность пространства фиксирована. Библиогр. 27.
Ключевые слова:
разбиение, последовательность, евклидово пространство, минимум суммы квадратов расстояний, NP-трудность, FPTAS.
Статья поступила: 15.09.2015 Переработанный вариант: 12.01.2016
Образец цитирования:
А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности”, Дискретн. анализ и исслед. опер., 23:2 (2016), 21–40; J. Appl. Industr. Math., 10:2 (2016), 209–219
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da843 https://www.mathnet.ru/rus/da/v23/i2/p21
|
Статистика просмотров: |
Страница аннотации: | 297 | PDF полного текста: | 49 | Список литературы: | 47 | Первая страница: | 2 |
|