Труды Института математики и механики УрО РАН
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды Института математики и механики УрО РАН, 2017, том 23, номер 4, страницы 301–310
DOI: https://doi.org/10.21538/0134-4889-2017-23-4-301-310
(Mi timm1489)
 

Неулучшаемая гарантированная оценка точности для задачи о $k$ медианах на отрезке $[0,1]$

М. Ю. Хачайabc, Д. М. Хачайab, В. С. Панкратовa

a Инcтитут математики и механики им. Н. Н. Красовского УрО РАН
b Уральский федеральный университет
c Омский государственный технический университет
Список литературы:
Аннотация: Одномерная задача кластеризации $k$-medians рассматривается в контексте игры двух лиц с нулевой суммой. Множество стратегий первого игрока совпадает с совокупностью выборок фиксированной длины из отрезка $[0,1]$. Стратегиями второго игрока являются всевозможные разбиения произвольной выборки данной длины на заданное число кластеров. В качестве платежной выступает функция, оценивающая качество кластеризации, значение которой численно совпадает с суммой уклонений элементов выборки от центров ближайших к ним кластеров. Как нетрудно убедиться, за исключением редких случаев данная игра не имеет цены. Для произвольных натуральных $n$ и $k$ строится верхняя оценка $0.5n/(2k-1)$ нижней цены игры. Обосновывается достижимость найденной оценки при $k>1$ и достаточно больших $n=n(k)$. Тем самым показывается, что для произвольной выборки длины $n$ может быть построена кластеризация методом $k$ медиан так, что значение платежной функции не превысит найденной оценки, причем данная оценка достижима при произвольном числе кластеров и выборок достаточно большой длины. Полученные результаты нашли применение в комбинаторной оптимизации при обосновании полиномиальной разрешимости подклассов труднорешаемых экстремальных задач.
Ключевые слова: кластеризация, задача о $k$ медианах, достижимая оценка точности.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 16-07-00266
17-08-01385
Исследования поддержаны Российским фондом фундаментальных исследований, гранты 16-07-00266 и 17-08-01385.
Поступила в редакцию: 22.09.2017
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.16 + 519.85
MSC: 90C27, 90C05, 62H30
Образец цитирования: М. Ю. Хачай, Д. М. Хачай, В. С. Панкратов, “Неулучшаемая гарантированная оценка точности для задачи о $k$ медианах на отрезке $[0,1]$”, Тр. ИММ УрО РАН, 23, № 4, 2017, 301–310
Цитирование в формате AMSBIB
\RBibitem{KhaKhaPan17}
\by М.~Ю.~Хачай, Д.~М.~Хачай, В.~С.~Панкратов
\paper Неулучшаемая гарантированная оценка точности для задачи о $k$ медианах на отрезке~$[0,1]$
\serial Тр. ИММ УрО РАН
\yr 2017
\vol 23
\issue 4
\pages 301--310
\mathnet{http://mi.mathnet.ru/timm1489}
\crossref{https://doi.org/10.21538/0134-4889-2017-23-4-301-310}
\elib{https://elibrary.ru/item.asp?id=30713983}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/timm1489
  • https://www.mathnet.ru/rus/timm/v23/i4/p301
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Труды Института математики и механики УрО РАН
    Статистика просмотров:
    Страница аннотации:223
    PDF полного текста:46
    Список литературы:32
    Первая страница:7
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024