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.