Учени от INSAIT постигнаха пробив в областта на графовите алгоритми и бяха удостоени с награда за най-добра статия на FOCS’24, водеща конференция по алгоритми и теория! Работата е съвместен проект между изследователи от INSAIT, ETH Zurich и Принстън. Наградата за най-добра статия беше получена измежду 133 приети статии на FOCS’24.
Резултатът е една от най-актуалните и дискутирани теми в компютърните науки през последните няколко дни. Това е и първият път от 65 години насам, в който българска организация приема доклади на FOCS!
Статията демонстрира изненадващи нови възможности на близо 70-годишния класически алгоритъм на Дейкстра, преподаван във всички уводни курсове по алгоритми и в основата на някои от най-използваните приложения в света – GPS, планиране на маршрути и др. Новият механизъм показва как алгоритъмът може да се използва за оптимално изчисляване на най-прекия маршрут, възможно най-бързо, когато се сблъскаме с каквато и да е графична задача (напр. логистика, реагиране при кризи и др.), без никакви отклонения!
Поздравления за всички автори: д-р Bernhard Haeupler (INSAIT и ETH), Richard Hladík (ETH, посетител в INSAIT), д-р Václav Rozhoň (INSAIT), д-р Jakub Tětek (INSAIT) и проф. Робърт Тарян (Принстън), носител на наградата Тюринг (еквивалент на Нобелова награда за компютърни технологии).
Освен тази работа, изследователите от INSAIT участват с 4 приети публикации на FOCS’24, включително статия от д-р Томаш Кочумака, нов преподавател по теория и алгоритми, който наскоро се присъедини към INSAIT от Макс-Планк. Поздравления на всички!
Връзка към статията: https://arxiv.org/pdf/2311.11793
Връзка към статия в списание Quanta, обясняваща резултата: https://www.quantamagazine.org/computer-scientists-establish-the-best-way-to-traverse-a-graph-20241025/