Введение
1 Истоки задач,ихтрактовкаиприложения 11
2 Кластеризация конечного множества точек евклидова пространства 27
2.1 Задача 2-кластеризации с оптимизируемыми мощностями кластеров 27
2.1.1 Формулировка задачи и известные результаты 27
2.1.2 Основы алгоритма 29
2.1.3 2-приближённый полиномиальный алгоритм 33
2.2 Задача 2-кластеризации с ограничениями на мощности кластеров 35
2.2.1 Формулировка задачи и известные результаты 35
2.2.2 Основы алгоритмов 37
2.2.3 Точный псевдополиномиальный алгоритм для специального случая задачи 38
2.2.4 Аппроксимационная схема 42
2.2.5 Рандомизированный алгоритм 49
3 Кластеризация конечной последовательности точек евклидова пространства 62
3.1 Задача 2-кластеризации 62
3.1.1 Формулировка задачи и известные результаты 62
3.1.2 Основы алгоритмов 64
3.1.3 Точный псевдополиномиальный алгоритм для специального случая задачи 67
3.1.4 Аппроксимационная схема 69
3.1.5 Рандомизированный алгоритм 73
3.2 Задачи многокластерного разбиения 77
3.2.1 Формулировки задач и известные результаты 77
3.2.2 Основы алгоритмов 79
3.2.3 2-приближённый алгоритм для задачи с ограничениями на мощности кластеров 87
3.2.4 2-приближённый алгоритм для задачи с оптимизируемыми мощностями кластеров 91
Заключение 95
Литература
