Plan seminariów w roku akademickim 2010/2011

Semestr II

2011.02.17 Spotkanie organizacyjne

2011.02.24 Wojciech Śmietanka
Model Multi-Core

2011.03.03 Kamil Kawka: XML

2011.03.10 Michał Pachucki
Stochastyczne algorytmy aproksymacyjne

2011.03.17 Marek Adamczyk
Przepływy w grafach planarnych

2011.03.24 Damian Karasiński
Algebraiczny dowód tw. Brooksa

2011.03.31 Michał Jastrzębski
Algorytmiczny Lemat Lokalny Lovasza

2011.04.07 Piotr Kufel
Implicit data structures

2011.04.21 Przemysław Horban
TBA

2011.04.28 Bartosz Górski
TBA

2011.05.05 Piotr Niedźwiedź
TBA

2011.05.12 Michał Kijewski
TBA

2011.05.19 Marian Marek Kędzierski
Maksymalna rozciągłość wzorców w XML-owej wymianie danych

Semestr zimowy

2010.10.07 Spotkanie organizacyjne

2010.10.14 i 2010.10.21 Marek Adamczyk
Greedy algorithm for stochastic matching is a 2-approximation
Streszczenie: The stochastic matching problem was first introduced by Chen, Immorlica, Karlin, Mahdian, and Rudra (ICALP 2009). They presented greedy algorithm together with an analysis showing that this is a 4-approximation. They also presented modification of this problem called multiple-rounds matching, and gave O(log n)-approximation algorithm. Many questions were remaining after this work: is the greedy algorithm a 2-approximation, is there a constant-ratio algorithm for multiple-rounds matching, and what about weighted graphs? For the last two problems constant-factor approximations were given in the work of Bansal, Gupta, Nagarajan, and Rudra, and in the work of Li and Mestre. In this paper we are answering to the first question by showing that the greedy algorithm is in fact a 2-approximation.
arXiv

2010.10.28 Kamil Kawka
Liczba inwersji w permutacji w czasie O(nloglogn)

2010.11.04,11.18 Michał Pachucki
Algorytmy FPT dla unit-disk graphs

2010.11.25 Marian Kędzierski
Sparsyfikacja grafów i nieskierowane przepływy

2010.12.09 Marek Adamczyk
Najkrótsze ścieżki w grafach planarnych z dodatnim i ujemnymi wagami

2010.12.16 Michał Pachucki
Algorytmy FPT dla problemu zbioru dominującego w grafach jednolicie rzadkich

2010.01.13 Wojciech Tyczyński
Automaty Boyera-Moore'a (?)

2010.01.20 Kamil Kawka