|
|
Колмогоровский семинар по сложности вычислений и сложности определений
26 марта 2012 г. 16:45–18:20, г. Москва, Главное здание МГУ, ауд. 16-04
|
 |
|
 |
|
|
|
Покрытия длинных кратчайших путей и их приложения
И. П. Разенштейн |
|
Аннотация:
Рассмотрим неориентированный взвешенный граф с уникальными кратчайшими путями. Будем изучать маленькие множества вершин, которые задевают все кратчайшие пути из $\epsilon n$ вершин. В докладе будут рассмотрены разные оценки на размеры этих множеств и будут рассказаны два конкретных приложения: точный оракул больших расстояний и вложение метрик в $\ell_1$, которое сохраняет большие расстояния. Результат про метрики дает некоторое улучшение алгоритма Лейтона–Рао для задачи о разреженном разрезе.
|
|
Обратная связь: