Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. UW

Information

Home page

List of talks

• Oct. 14, 2010, 12:15 p.m.
  Jakub Pawlewicz (Uniwersytet Warszawski)
  Zliczanie liczb bezkwadratowych
  Liczba bezkwadratowa, to taka, która nie ma dzielników kwadratowych Liczenie liczby liczb bezkwadratowych nie większych od n dotychczas potrafiliśmy robić w czasie O(n^1/2). Przedstawię algorytm działający w czasie O(n^2/5) w pamięci O(n^1/5), który dodatkowo dobrze …

  ---

• Oct. 7, 2010, 12:15 p.m.
  Jaroslaw Byrka (Uniwersytet Wrocławski)
  An Improved LP-based Approximation for Steiner Tree
  The Steiner tree problem is: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was …

  ---

• Oct. 9, 2008, 12:15 p.m.
  Piotr Sankowski (Uniwersytet Warszawski)
  Lokalne koalicje w grach na sieciach
  Jakosc equilibrium Nasha w grach na sieciach zostala juz dobrze zrozumiana i seminarium zaczne od wprowadzenia problmu i przypomnienia najwazniejszych wynikow. Natomiast glownym tematem saminarium bedzie cena anarchii w grzach na sieci z kosztem Shaplya, …

  ---

• Nov. 29, 2007, 12:15 p.m.
  David Peleg (Weizmann Institute)
  On time-efficient broadcast in wireless networks
  As broadcasting is one of the primary functions in radio networks, fast algorithms for performing it are of considerable interest. A radio network consists of stations that can act at any a given time step …

  ---

• Oct. 4, 2007, 4:15 p.m.
  Madhu Sudan (Massachusetts Institute of Technology)
  Sub-linear time algebraic algorithms
  A modern thrust in computing is to design algorithms that take vast amounts of data and try to estimate properties of the data in a "quick and dirty" way. Sub-linear time algorithms is the area …

  ---

• March 8, 2007, 12:15 p.m.
  Uri Zwick (Tel Aviv University)
  prowadzi: Uri Zwick (Overhang)
  How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of (1/2)H_n, where H_n=1/1+1/2+...+1/n is the n-th harmonic number. This …

  ---

• Jan. 11, 2007, 12:15 p.m.
  Darek Kowalski ( University of Liverpool)
  Zlozonosc komunikacyjna algorytmow rozproszonych odpornych na wady
  Przedstawie dwa podstawowe problemy rozproszone: consensus (decyzyjny) oraz gossip (komunikacyjny). Zaprezentuje szereg rozwiazan dla tych problemow ktore sa: odporne na wady (typu crash), szybkie oraz generujace niewielka ilosc komunikatow. Wiekszosc dotychczasowych algorytmow byla z reguly …

  ---

• Dec. 14, 2006, 12:15 p.m.
  Arkadiusz Paterek (Uniwersytet Warszawski)
  Collaborative Filtering: Netflix Prize
  In this talk, I will present different algorithms for the collaborative filtering task. The task of collaborative filtering is to predict the preferences of a user, given preferences of other users. An example of a …

  ---

• Oct. 26, 2006, 12:15 p.m.
  Marcin Mucha (Uniwersytet Warszawski)
  Aproksymacja asymetrycznych wariantow problemu komiwojazera
  Na najblizszym seminarium opowiem prace Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko "Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs". J. ACM 52(4): 602-626 (2005) (wczesniej extended abstract na FOCS 2003). Autorzy …

  ---

• Oct. 12, 2006, 12:15 p.m.
  Łukasz Kowalik (Uniwersytet Warszawski)
  Konferencja SODA; "Mierz i zwyciężaj": metoda analizy algorytmów wykładniczych.
  Seminarium będzie się składało z dwóch części. Podczas części pierwszej krótko przedstawię najciekawsze wyniki z tegorocznej konferencji SODA. Nieco bardziej szczegółowo opowiem o pracy Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch, "Measure and Conquer: A …

  ---

• May 25, 2006, 12:15 p.m.
  Bartosz Przydatek (ETH w Zurychu)
  Solving Medium-Density Subset Sum Problems in Expected Polynomial Time
  Solving Medium-Density Subset Sum Problems in Expected Polynomial Time. The subset sum problem (SSP) (given n numbers and a target bound B, find a subset of the numbers summing to B), is a classic NP-hard …

  ---

• May 11, 2006, 12:15 p.m.
  Piotr Sankowski (Uniwersytet Warszawski)
  Szybsze dynamiczne skojarzenia i spójność wierzchołkowa
  W ramach seminarium opowiem o pierwszych dynamicznych podkwadratowych algorytmach na obliczanie: liczby wierzchołkowo rozłącznych s,t-ścieżek, rozmiaru maksymalnego skojarzenia w grafie i skierowanej k-spójności wierzchołkowej. Prezentowane algorytmy są randomizowane z jednostronnym błędem. Algorytmy dynamiczne dla problemu …

  ---

• March 9, 2006, 12:15 p.m.
  Marcin Kubica i Tomasz Waleń (Uniwersytet Warszawski)
  O pewnych algorytmicznych problemach tekstowych
  Tomek Waleń opowie o wspólnej pracy z P. Kolmanem. Podczas seminarium zostanie przybliżony problem porównywania sekwencji genomów. W szczególności problem obliczania odległości pomiędzy napisami liczonej w liczbie odwróceń (całych bloków), potrzebnych do przekształcenia jednego napisu …

  ---

• March 2, 2006, 12:15 p.m.
  Wojciech Plandowski (Uniwersytet Warszawski)
  O rozwiązywaniu równań w półgrupie wolnej
  Na seminarium przedstawię pierwszy algorytm rozwiązujący równania w półgrupie wolnej, który działa w DEXPTIME. Prezentowane podejście pozwala na rozwiązanie w PSPACE następujących problemów: - sprawdzenia, czy zbiór rozwiązań równania jest skończony, - sprawdzenia, czy zbiór …

  ---

• Jan. 26, 2006, 12:15 p.m.
  Anna Wojak (Uniwersytet Warszawski)
  Wyznaczanie Euklidesowej najkrótszej drogi na płaszczyźnie pomiędzy dwoma punktami z pominięciem wielokątnych przeszkód.
  Wyznaczanie Euklidesowej najkrótszej ścieżki jest jednym z najstarszych i dobrze znanych problemów w geometrii obliczeniowej. Obecnie istnieje wiele typów problemów związanych z wyznaczaniem najkrótszych dróg. Rozważmy płaszczyznę zawierająca zbiór rozłącznych przeszkód, których liczba wierzchołków wynosi …

  ---