Shortest paths - exact and approximate algorithms

Prowadzi: Prof. Uri Zwick (Tel Aviv University).

O wykładowcy | Streszczenie | Materiały dla studentów | Zadania zaliczeniowe

O wykładowcy: Uri Zwick jest profesorem Wydziału Informatyki Uniwersytetu w Tel Avivie, którym kierował w latach 2000-2002. Wcześniej wykładał i prowadził badania m. in. w University of Warwick (Anglia) oraz University of California in Berkeley (USA). Jest autorem ponad 100 prac naukowych w dziedzinie algorytmiki, opublikowanych w najlepszych światowych czasopismach. Ma na swoim koncie szeroko znane wyniki z takich dziedzin jak randomizacja czy algorytmy dla problemów najkrótszych ścieżek w grafach. Wielokrotnie był członkiem komitetów programowych czołowych konferencji z informatyki teoretycznej takich jak ICALP, SODA czy FOCS, a w 2003 roku kierował pracami komitetu programowego konferencji ESA. Wypromował sześciu doktorów.

Streszczenie: The two lectures of the mini-course would cover exact and approximate algorithms for the all-pairs shortest paths problem and some of its variants. The first lecture would focus on exact algorithms for the all-pairs shortest paths problem that rely on the use of fast matrix multiplication algorithms. The second lecture would focus on faster combinatorial algorithms for approximating distances. Distance oracles and spanners would also be considered.

Materiały dla studentów:

Zadania zaliczeniowe [PDF]
Prosimy o przesyłanie rozwiazan w plikach PDF na adres zwick at tau dot ac dot il do 31 maja 2007.