Максимальный поток и поток с минимальной стоимостью за почти линейное время
https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/
Researchers Achieve ‘Absurdly Fast’ Algorithm for Network Flow | Quanta Magazine
Computer scientists can now solve a decades-old problem in practically the time it takes to write
Команда ученых-компьютерщиков разработала значительно более быстрый алгоритм для одной из старейших задач в информатике: максимального потока. Задача заключается в том, сколько материала может пройти по сети от источника к месту назначения, если каналы в сети имеют ограничения пропускной способности.
Новый алгоритм «абсурдно быстр», — сказал Дэниел Спилман из Йельского университета. «На самом деле я был склонен полагать, что алгоритмов, настолько хороших для решения этой задачи, просто не существует».
Максимальный поток и поток с минимальной стоимостью за почти линейное время
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
https://arxiv.org/abs/2203.00671
Researchers Achieve ‘Absurdly Fast’ Algorithm for Network Flow | Quanta Magazine
Computer scientists can now solve a decades-old problem in practically the time it takes to write
Команда ученых-компьютерщиков разработала значительно более быстрый алгоритм для одной из старейших задач в информатике: максимального потока. Задача заключается в том, сколько материала может пройти по сети от источника к месту назначения, если каналы в сети имеют ограничения пропускной способности.
Новый алгоритм «абсурдно быстр», — сказал Дэниел Спилман из Йельского университета. «На самом деле я был склонен полагать, что алгоритмов, настолько хороших для решения этой задачи, просто не существует».
Максимальный поток и поток с минимальной стоимостью за почти линейное время
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
https://arxiv.org/abs/2203.00671