Organizatorzy

dr hab. Michał Pilipczuk, prof. ucz.

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://semalgo.wordpress.com/

Lista referatów

16 grudnia 2010 12:15
Krzysztof Onak (CMU)
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
We present a near-linear time algorithm for approximating the edit distance between two strings to within a significantly better factor than previously known. This result emerges in our investigation of edit distance from a new …
9 grudnia 2010 12:15
Łukasz Kowalik (Uniwersytet Warszawski)
Cykl Hamiltona w grafach nieskierowanych szybciej niz 2^n.
Problemy cyklu Hamiltona i TSP to jedne z najintensywniej badanych problemow optymalizacyjnych. W latach 60-tych Held i Karp podali prosty algorytm oparty na programowaniu dynamicznym, wymagajacy czasu O*(2^n) i pamieci O(2^n). Powstalo naturalne pytanie, czy …
2 grudnia 2010 12:15
Maxime Crochemore (King's College London)
Reactive Automata
25 listopada 2010 12:15
Bartlomiej Bosek i Tomasz Krawczyk (Uniwersytet Jagielloński)
The sub-exponential upper bound for the on-line chain partitioning problem
One of the important models for scheduling is based on partially ordered sets. In this model the points represent the incoming tasks and the order reflects cause-effect relation between tasks. The algorithmic problem which arises …
4 listopada 2010 12:15
Marcin Pilipczuk (Uniwersytet Warszawski)
Unique Games Conjecture i trudność aproksymacji
Począwszy od sławnego twierdzenia PCP, do dnia dzisiejszego znamy bardzo dużo wyników dowodzących trudność aproksymacji różnych problemów. O ile dowodzenie braku istnienia PTASa jest zazwyczaj mniej lub bardziej skomplikowaną redukcją kombinatoryczną, o tyle otrzymani ścisłych …
21 października 2010 12:15
Jakub Łącki (Uniwersytet Warszawski)
Dynamiczne algorytmy dla silnie spójnych składowych i domknięcia przechodniego
Zaprezentuję strukturę danych, która utrzymuje strukturę silnie spójnych składowych grafu skierowanego i obsługuje operacje usunięć krawędzi. Przy jej użyciu pokażę algorytm utrzymywania domknięcia przechodniego podczas usuwania krawędzi z grafu. Działa on deterministycznie i jest równie …
14 października 2010 12:15
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 …
7 października 2010 12:15
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 …
9 października 2008 12:15
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, …
29 listopada 2007 12:15
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 …
4 października 2007 16:15
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 …
8 marca 2007 12:15
Uri Zwick (Tel Aviv University)
Overhang (prowadzi: Uri Zwick)
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 …
11 stycznia 2007 12:15
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 …
14 grudnia 2006 12:15
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 …
26 października 2006 12:15
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 …