Учёный в области информатики преодолел ограничение, существовавшее с 1996 года
Новый алгоритм Маноя Гупты обеспечивает гарантию 2-приближения для близких вершин, не увеличивая время работы
Короткое резюме
Учёный Маной Гупта из Индийского института технологии Гандинагар представил на симпозиуме FOCS 2025 алгоритм, который решает давнюю проблему в задаче всех пар кратчайших путей (APSP). Новый метод распространяет гарантию 2-приближения на близкие пары вершин, сохраняя почти оптимальное время работы, что не удавалось с 1996 года.
Задача APSP важна для транспорта, связи и биологии. В 1996 году алгоритм ДХЗ давал 2-приближение только для достаточно далёких точек, поскольку сэмплирование вершин не позволяло находить короткие пути. Гупта решил проблему с помощью многоуровневого сэмплирования, которое анализирует связи на разных масштабах и учитывает короткие маршруты, не увеличивая сложность.
Хотя результаты теоретические, они укрепляют основы алгоритмов для больших сетей — от интернета до ИИ. Улучшение влиятельного результата 1996 года без потери скорости представляет значительный прогресс, позволяя надёжнее оценивать расстояния в огромных сетях и лучше понимать их структуру.
Расширение гарантии 2-приближения
Алгоритм Гупты обеспечивает точность «не более чем в два раза» для близких пар вершин, что ранее было невозможно
Сохранение вычислительной сложности
Новый метод не увеличивает время работы по сравнению с алгоритмом ДХЗ 1996 года
Многоуровневое сэмплирование
Ключевая идея — анализ сетевых связей на нескольких масштабах для учёта коротких маршрутов
Теоретическая и практическая значимость
Работа важна для анализа больших сетей, хотя пока не ведёт к немедленным улучшениям коммерческих систем
Текст сгенерирован с использованием ИИ
