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




  • скачать файл:
  • Название:
  • Аппроксимируемость труднорешаемых геометрических задач кластеризации и маршрутизации Шенмайер Владимир Владимирович
  • Альтернативное название:
  • Approximability of difficult geometric problems of clustering and routing Shenmaier Vladimir Vladimirovich
  • Кол-во страниц:
  • 264
  • ВУЗ:
  • Ин-т математики им. С.Л. Соболева
  • Год защиты:
  • 2019
  • Краткое описание:
  • Шенмайер, Владимир Владимирович.
    Аппроксимируемость труднорешаемых геометрических задач кластеризации и маршрутизации : диссертация ... доктора физико-математических наук : 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
    Заключение
    Литература
  • Список литературы:
  • -
  • Стоимость доставки:
  • 230.00 руб


ПОИСК ДИССЕРТАЦИИ, АВТОРЕФЕРАТА ИЛИ СТАТЬИ


Доставка любой диссертации из России и Украины


ПОСЛЕДНИЕ СТАТЬИ И АВТОРЕФЕРАТЫ

ГБУР ЛЮСЯ ВОЛОДИМИРІВНА АДМІНІСТРАТИВНА ВІДПОВІДАЛЬНІСТЬ ЗА ПРАВОПОРУШЕННЯ У СФЕРІ ВИКОРИСТАННЯ ТА ОХОРОНИ ВОДНИХ РЕСУРСІВ УКРАЇНИ
МИШУНЕНКОВА ОЛЬГА ВЛАДИМИРОВНА Взаимосвязь теоретической и практической подготовки бакалавров по направлению «Туризм и рекреация» в Республике Польша»
Ржевский Валентин Сергеевич Комплексное применение низкочастотного переменного электростатического поля и широкополосной электромагнитной терапии в реабилитации больных с гнойно-воспалительными заболеваниями челюстно-лицевой области
Орехов Генрих Васильевич НАУЧНОЕ ОБОСНОВАНИЕ И ТЕХНИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ ЭФФЕКТА ВЗАИМОДЕЙСТВИЯ КОАКСИАЛЬНЫХ ЦИРКУЛЯЦИОННЫХ ТЕЧЕНИЙ
СОЛЯНИК Анатолий Иванович МЕТОДОЛОГИЯ И ПРИНЦИПЫ УПРАВЛЕНИЯ ПРОЦЕССАМИ САНАТОРНО-КУРОРТНОЙ РЕАБИЛИТАЦИИ НА ОСНОВЕ СИСТЕМЫ МЕНЕДЖМЕНТА КАЧЕСТВА