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

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

Адрес Издательства СО РАН: Россия, 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] => 54.173.221.132
    [SESS_TIME] => 1711632841
    [BX_SESSION_SIGN] => 9b3eeb12a31176bf2731c6c072271eb6
    [fixed_session_id] => 43400e8b49174a101624f45877d4259c
    [UNIQUE_KEY] => ecfb7a02fea3db089b8b934a82e1fcac
    [BX_LOGIN_NEED_CAPTCHA_LOGIN] => Array
        (
            [LOGIN] => 
            [POLICY_ATTEMPTS] => 0
        )

)

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

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

2017 год, номер 1

О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств

А.Е. Галашов1, А.В. Кельманов1,2
1Новосибирский национальный исследовательский государственный университет, ул. Пирогова, 2, Новосибирск, 630090
galashov.alexandr@gmail.com
2Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук
kelm@math.nsc.ru
Ключевые слова: поиск подмножеств, кластерный анализ, евклидово пространство, минимум суммы квадратов расстояний, NP-трудная задача, точный псевдополинимиальный алгоритм, Euclidean space, subsets search, clustering, NP-hard problem, exact pseudopolynomial-time algorithm
Страницы: 15-22

Аннотация

Рассматривается NP-трудная в сильном смысле задача поиска в конечном множестве точек евклидова пространства семейства непересекающихся подмножеств, имеющих заданные мощности. Критерием решения задачи является минимум суммы по всем подмножествам сумм квадратов расстояний от элементов подмножеств до их геометрических центров. Доказано, что задача разрешима за псевдополиномиальное время, если координаты входных точек целочисленны, а размерность пространства и число искомых подмножеств фиксированы (ограничены константами).

DOI: 10.15372/SJNM20170102