• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Версия для слабовидящихВерсия для слабовидящихЛичный кабинет сотрудника ВШЭПоиск
Расширенный поиск
Меню
Высшая школа экономики

Эффективные алгоритмы для решения задач о заданном порядковом расстоянии, о геометрическом минимальном остовном дереве и о максиминных путяхEfficient algorithms to solve problems on a given order distance, on the geometric minimum spanning tree, and on maximin paths

Соискатель:
Каймаков Кирилл Владимирович
Члены комитета:
Райгородский Андрей Михайлович (МФТИ, д.ф.-м.н., председатель комитета), Абросимов Михаил Борисович (Саратовский государственный университет имени Н.Г. Чернышевского, д.ф.-м.н., член комитета), Жуковский Максим Евгеньевич (Университет г. Шеффилд (Великобритания), д.ф.-м.н., член комитета), Николаев Андрей Валерьевич (Ярославский государственный университет им. П.Г. Демидова , д.ф.-м.н., член комитета), Тараненко Анна Александровна (Институт математики имени С.Л. Соболева СО РАН, к.ф.-м.н., член комитета)
Диссертация принята к предварительному рассмотрению:
2/27/2025
Диссертация принята к защите:
3/27/2025
Дисс. совет:
Совет по компьютерным наукам
Дата защиты:
6/23/2025
Диссертация посвящена разработке эффективных алгоритмов для приближенного вычисления  порядкового расстояния по -норме в системе точек единичного квадрата; поиска минимального остовного дерева на точках мерного пространства в -норме; решения онлайновой и офлайновой задач о  максиминных путях на заданной сети; вычисления верхнего и нижнего допусков произвольного ребра в инъективной задаче о максиминном пути. Полученные в диссертации результаты улучшают сложности алгоритмов Ленхова-Шмида, Габоу-Бентли-Тарджана, Рамасвами-Орлина-Чакраварти.
Диссертация [*.pdf, 4.39 Мб] (дата размещения 4/3/2025)
Резюме [*.pdf, 251.13 Кб] (дата размещения 4/3/2025)
Summary [*.pdf, 237.65 Кб] (дата размещения 4/3/2025)

Публикации, в которых излагаются основные результаты диссертации

Каймаков К.В., Малышев Д.С. Приближенный поиск k-ого порядкового расстояния в системе точек единичного квадрата (смотреть на сайте журнала)
Каймаков К.В., Малышев Д.С. Эффективный поиск минимального дерева на точках пространства в l1-норме (смотреть на сайте журнала)


Отзывы
Отзыв научного руководителя
Отзыв члена Комитета
Сведения о результатах защиты:
Комитет по диссертации рекомендовал присудить ученую степень кандидата наук (протокол № 2 от 23.06.2025). Решением диссертационного совета (протокол № 6 от 26.06.2025) присуждена ученая степень кандидата компьютерных наук.