Семинары: М. Ю. Хачай, Достижимая гарантия качества кластеризации методом k-медиан на отрезке [0,1]

СЕМИНАРЫ


Семинар отдела математического программирования 13 октября 2017 г. 12:00, г. Екатеринбург, Институт математики и механики им. Н. Н. Красовского УрО РАН, ул. Софьи Ковалевской 16, актовый зал

Достижимая гарантия качества кластеризации методом k-медиан на отрезке [0,1] М. Ю. Хачай^ab ^a Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург ^b Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
Аннотация: Исследуется одномерная задача кластеризации методом k медиан в контексте антагонистической игры, стратегиями игроков которой являются n-элементная выборка из отрезка [0,1] и разбиение ее на k кластеров, соответственно. Для произвольной выборки длины n и произвольного фиксированного числа k>1, приводится неулучшаемая оценка наилучшего качества кластеризации 0.5n/(2k-1), совпадающая с нижней ценой этой игры.