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