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

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

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

)

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

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

2019 год, номер 2

Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 2-кластеризации

А.В. Кельманов1,2, А.В. Панасенко1,2, В.И. Хандеев1,2
1Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, Новосибирск, 630090, Россия
kelm@math.nsc.ru
2Новосибирский национальный исследовательский государственный университет, Новосибирск, 630090, Россия
a.v.panasenko@math.nsc.ru
Ключевые слова: евклидово пространство, 2-кластеризация, наибольшее подмножество, NP-трудность, целочисленная задача, псевдополиномиальная разрешимость, Euclidean space, 2-clustering, largest subset, NP-hardness, exact algorithm, pseudo- polynomial-time solvability
Страницы: 121-136

Аннотация

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

DOI: 10.15372/SJNM20190201