Издательство СО РАН

Издательство СО РАН

Адрес Издательства СО РАН: Россия, 630090, а/я 187
Новосибирск, Морской пр., 2

soran2.gif

Baner_Nauka_Sibiri.jpg


Яндекс.Метрика

Array
(
    [SESS_AUTH] => Array
        (
            [POLICY] => Array
                (
                    [SESSION_TIMEOUT] => 24
                    [SESSION_IP_MASK] => 0.0.0.0
                    [MAX_STORE_NUM] => 10
                    [STORE_IP_MASK] => 0.0.0.0
                    [STORE_TIMEOUT] => 525600
                    [CHECKWORD_TIMEOUT] => 525600
                    [PASSWORD_LENGTH] => 6
                    [PASSWORD_UPPERCASE] => N
                    [PASSWORD_LOWERCASE] => N
                    [PASSWORD_DIGITS] => N
                    [PASSWORD_PUNCTUATION] => N
                    [LOGIN_ATTEMPTS] => 0
                    [PASSWORD_REQUIREMENTS] => Пароль должен быть не менее 6 символов длиной.
                )

        )

    [SESS_IP] => 98.84.18.52
    [SESS_TIME] => 1728557073
    [BX_SESSION_SIGN] => 9b3eeb12a31176bf2731c6c072271eb6
    [fixed_session_id] => 00cdd48daa3a4af1293c2e331dfba4dc
    [UNIQUE_KEY] => db280185232bdf37e22aa0ea5f27d08d
    [BX_LOGIN_NEED_CAPTCHA_LOGIN] => Array
        (
            [LOGIN] => 
            [POLICY_ATTEMPTS] => 0
        )

)

Поиск по журналу

Сибирский журнал вычислительной математики

2017 год, номер 4

Аппроксимационная схема для задачи поиска подпоследовательности

А.В. Кельманов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