Покрытия длинных кратчайших путей и их приложения.
Аннотация
Рассмотрим неориентированный взвешенный граф с уникальными кратчайшими
путями. Будем изучать маленькие множества вершин, которые задевают все
кратчайшие пути из $\epsilon n$ вершин. В докладе будут рассмотрены разные
оценки на размеры этих множеств и будут рассказаны два конкретных приложения:
точный оракул больших расстояний и вложение метрик в $\ell_1$, которое
сохраняет большие расстояния. Результат про метрики дает некоторое улучшение
алгоритма Лейтона - Рао для задачи о разреженном разрезе.