Logowanie

Języki

  • Polski
  • English

Seminarium ZZOiA: Damian straszak o technikach analitycznych w algorytmice  

Najbliższe seminarium ZZOiAA odbędzie się wyjątkowo w poniedziałek, 26 października, o godz. 14.15 w sali 141. Damian Straszak opowie o technikach analitycznych w algorytmice.

Abstrakt: W ostatnich latach można zaobserwować rosnące zainteresowanie technikami analitycznymi w konstrukcji algorytmów. Wychodząc od problemów natury czysto kombinatorycznej takich jak max-flow, maximum matching, sparsest cut rozważamy ich ciągłe relaksacje w postaci programów liniowych, kwadratowych i ogólniej wypukłych. To pozwala nam przejść od dyskretnej do ciągłej przestrzeni rozwiązań, a w niej (w wielu przypadkach) potrafimy się poruszać znacznie efektywniej. Wiele spektakularnych wyników osiągniętych w ostatnich latach opiera się właśnie na tej idei, wśród nich m.in. najszybszy znany algorytm dla problemu max-flow (Lee, Sidford '14) oraz bipartite matching (Mądry '13). Podczas referatu chciałbym omówić te i pokrewne wyniki, naszkicować stosowane techniki, w szczególności kluczowe narzędzie, jakim jest niemal liniowy algorytm do rozwiązywania ważnej klasy układów równań (Spielman, Teng '04).

Adres:
Instytut Informatyki
Uniwersytetu Wroclawskiego
ul. Joliot-Curie 15
50-383 Wroclaw
Sekretariat
tel.: 71 375 7800
tel.: 71 325 1271
fax: 71 375 7801
sekretariat@ii.uni.wroc.pl
Dziekanat
tel.: 71 375 7892
dziekan@ii.uni.wroc.pl
sprawy studenckie:
dziekanat@ii.uni.wroc.pl
Portiernia
tel.: 71 375 7958
Redaktor strony WWW
redaktor@ii.uni.wroc.pl
Projekt
MAKOS