Аппроксимируемость труднорешаемых геометрических задач кластеризации и маршрутизации Шенмайер Владимир Владимирович

Краткое описание

Шенмайер, Владимир Владимирович.
Аппроксимируемость труднорешаемых геометрических задач кластеризации и маршрутизации : диссертация ... доктора физико-математических наук : 01.01.09 / Шенмайер Владимир Владимирович; [Место защиты: Ин-т математики им. С.Л. Соболева]. - Новосибирск, 2019. - 264 с. : ил.
Оглавление диссертациидоктор наук Шенмайер Владимир Владимирович
1.1 Модель вычислений
1.2 Real RAM и машины Тьюринга
1.3 Элементы теории сложности
1.4 Фиксированные параметры геометрических задач
2 Задачи о подмножестве минимального геометрического размера
2.1 Аппроксимация задачи k-Variance
2.1.1 Метод аффинных оболочек
2.1.2 Дискретизация алгоритма
2.2 Аппроксимация задачи 2-Means с фиксированным центром одного
из кластеров
2.2.1 Приближённая схема, основанная на методе аффинных оболочек
2.2.2 Взвешенная версия задачи FC2-Means
2.3 Сложность и аппроксимация задачи о минимальном шаре, охватывающем k точек
2.3.1 Сложность евклидовой задачи
2.3.2 Сложность задачи в пространстве с нормой
2.3.3 Приближённый алгоритм для метрического случая
2.3.4 Приближённая схема для случая пространства малой размерности
3 Задача о подмножестве векторов с суммой максимальной длины
3.1 Аппроксимируемость задачи суммирования векторов в пространстве произвольной размерности
3.1.1 Матричные нормы и задачи Гротендика
3.1.2 Эквивалентность задач ЬУБ и МКС
3.1.3 Сведение задачи о максимальном разрезе
3.1.4 Аппроксимируемость задачи ЬУБ в случае норм £р
3.1.5 Сведение задачи ЬУВ^) к задаче ЬУ8(£р)
3.2 Сложность задачи о к-элементной сумме векторов
3.2.1 Параметризованная сложность задачи с нормой £р
3.2.2 Сведение задачи о максимальном к-покрытии множествами
3.3 Рандомизированная приближённая схема для случая пространства малой размерности
3.3.1 Описание алгоритма
3.3.2 Обоснование алгоритма
3.4 Точный алгоритм для задачи ЬУБ
3.4.1 Допустимые решения специального вида
3.4.2 Конфигурации гиперплоскостей
3.4.3 Алгоритм перечисления допустимых решений специального вида в двумерном случае
3.4.4 Алгоритм перечисления допустимых решений специального вида в многомерном случае
3.5 Точные алгоритмы для задачи Ьк-УВ
3.5.1 Допустимые решения специального вида
3.5.2 Алгоритм перечисления допустимых решений специального вида
3.5.3 Двумерный случай
3.5.4 Следствия для задачи FC2-Means
4 Геометрические задачи о последовательности медиан
4.1 Аппроксимация одномерной инкрементной задачи о медиане
4.1.1 Описание алгоритма
4.1.2 Обоснование рекуррентного соотношения
4.2 Аппроксимация евклидовой инкрементной задачи о медиане
4.2.1 Описание алгоритма
4.2.2 Обоснование рекуррентного соотношения
4.3 Аппроксимация евклидовой иерархической задачи о медиане
4.3.1 Описание алгоритма
4.3.2 Обоснование алгоритма
5 Геометрическая задача коммивояжёра на максимум и её модификации
5.1 Асимптотически точный алгоритм для геометрической задачи Max TSP
5.1.1 Описание алгоритма
5.1.2 Обоснование алгоритма
5.1.3 Приближённая схема PTAS
5.2 Задача о нескольких бродячих торговцах
5.2.1 Полиэдральные пространства
5.2.2 Асимптотически точный алгоритм
5.3 Задача о цикловом покрытии с ограничениями на количество и
длину циклов
5.3.1 Тоннельные метрики
5.3.2 Характеризация допустимых решений в терминах тоннельных систем
5.3.3 Алгоритм решения задачи Max-(c, k)-DCC
Заключение
Литература