Семинар "Highway Dimension and Provably Efficient Shortest Path Algorithms", Эндрю Голдберг

3 февраля 2010, 14:56

Сегодня мы открываем регистрацию на следующий семинар, который состоится 10 февраля 2010 года, в московском офисе Яндекса.

В рамках цикла семинаров «Информационный поиск и анализ данных» выступит Эндрю Голдберг из Microsoft Research.

Тема доклада: Highway Dimension and Provably Efficient Shortest Path Algorithms

О чём: Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, in real time, and with very low storage overhead. We give the first theoretical analysis of several underlying algorithms on a non-trivial class of networks. To do this, we introduce the notion of highway dimension. Our analysis works for networks with low highway dimension and gives a unified explanation of good performance for several seemingly different algorithms. Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck.

О докладчике: Andrew Goldberg is a Principal Researcher at Microsoft Research - Silicon Valley. His research interests include design, analysis, and experimental evaluation of algorithms, data structures, algorithm engineering, and computational game theory. Goldberg received his Ph.D. degree in Computer Science from M.I.T. in 1987. He also holds a B.S. degree from M.I.T. and an M.S. degree from U.C. Berkeley. Before joining Microsoft, he worked for Stanford University, NEC Research Institute, and InterTrust STAR Lab. His graph algorithms are taught in computer science and operations research classes and their implementations are widely used in industry and academia. Goldberg received a number of awards, including the NSF Presidential Young Investigator Award, the ONR Young Investigator Award, and the Mathematical Programming Society A.W. Tucker Prize. He is an ACM Fellow.

Задать вопросы докладчику и обсудить заявленную тему вы можете в Клубе.

Регистрация закрыта.

Начало мероприятия в 18:30, а подтвердить регистрацию вы можете с 18.00 (лучше прийти к этому времени, чтобы успеть к началу лекции).

Семинар будет транслироваться в Екатеринбурге, на матмехе УрГУ (ул. Тургенева, 4, ауд. 507), начало – 20:30 по местному времени.

Юлия Симутенко, обучаем и развиваем

1 комментарий
Подписаться на комментарии к посту
По-моему он всё-таки Андрей, не? В РАНе он вполне себе на русском этот доклад делал...