Эффективные алгоритмы решения некоторых задач вычислительной геометрии и комбинаторной оптимизации (Кирилл Каймаков)

Семинар международной лаборатории теоретической информатики ФКН Структуры данных играют ключевую роль в оптимизации алгоритмов, позволяя эффективно хранить информацию и получать к ней доступ. Правильный выбор структуры данных может значительно сократить время выполнения алгоритма, особенно при обработке больших объемов данных. В докладе на основе эффективного использования структур данных и комбинирования алгоритмических приемов предлагаются несколько алгоритмов для решения некоторых задач комбинаторной оптимизации и вычислительной геометрии, улучшающих ранее известные решения. В частности, в некотором смысле улучшаются результаты Габоу — Бентли — Тарджана для вычисления минимального остовного дерева на точечных данных в l1-норме и Рамасвами — Орлина — Чакраварти для анализа чувствительности оптимальных решений в задаче о максиминном пути. Выступает Кирилл Каймаков, аспирант департамента анализа данных и искусственного интеллекта ФКН ВШЭ. 28 ноября 2024 Международная лаборатория теоретической информатики: ФКН: ​​