Аппроксимационная схема для задачи поиска подпоследовательности
А.В. Кельманов1,2, С.М. Романченко1, С.А. Хамидуллин1
1Институт математики им. С.Л. Соболева СО РАН, просп. Акад. В.А. Коптюга, 4, Новосибирск, 630090
kelm@math.nsc.ru
2Новосибирский национальный исследовательский государственный университет, ул. Пирогова, 2, Новосибирск, 630090
Ключевые слова: последовательность, евклидово пространство, минимум суммы квадратов расстояний, -трудность, FPTAS, euclidean space, sequence, minimum sum of squared distances, -hardness, FPTAS
Страницы: 379-392
Аннотация
Рассматривается -трудная в сильном смысле задача поиска подпоследовательности с заданным числом элементов в конечной последовательности точек евклидова пространства. Критерием решения является минимум суммы квадратов расстояний от элементов искомой подпоследовательности до их геометрического центра. Выбор элементов подпоследовательности подчинен условию: разность между номерами последующего и предыдущего искомых элементов ограничена сверху и снизу заданными константами. Предложен приближенный алгоритм решения задачи. Доказано, что он является полностью полиномиальной аппроксимационной схемой (FPTAS), если размерность пространства ограничена константой.
DOI: 10.15372/SJNM20170403 |
