Algorytmy randomizowane i aproksymacyjne

wtorek: 16:15 - 17:45, sala 0083

Seminarium magisterskie poświęcone nasŧepującym zagadnieniom:
1) Gry strategiczne na grafach - rozgrywana liczba kolorująca, chromatyczna i zachłanna.
2) Geometryczne grafy przecięć (problemy rozpoznawania i rozszerzania częściowych reprezentacji).
3) Algorytmy kolorowania grafów z list, w tym kolorowanie z list on-line (paintability of graphs) i algorytmy strumieniowe (streaming algorithms).
4) Randomizowane algorytmy kolorowania hipergrafów.

20.11.2018 16:15
Dawid Tracz
Finding Cliques in Social Networks: A New Distribution-Free Model (Fox, Roughgarden, Seshadhri, Wei, Wein)
27.11.2018 16:15
Dominika Salawa
Induced trees in graphs of large chromatic number (Scott)

Poprzednie referaty

13.11.2018 16:15
Mateusz Pabian
New approximation algorithm for (1,2)-TSP (Adamaszek, Mnich, Paluch)
06.11.2018 16:15
Szymon Łukasz
NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors (A. Bhangale)

We give very short and simple proofs of the following statements: Given a 2-colorable 4-uniform hypergraph on n vertices,

1) It is NP-hard to color it with log^delta n colors for some delta>0.

2) It is quasi-NP-hard to color it with O({log^{1-o(1)} n}) colors.

30.10.2018 16:15
Wiktor Daniec
David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5)
David Galvin, “Three tutorial lectures on entropy and counting” (rozdział 5)
14.04.2015
Maciej Solon
Graphs defined by forbidden patterns.
 
13.01.2015
Andrzej Dorobisz.
Treewidth. Courcelle's theorem.
 
16.12.2014
Grzegorz Gutowski.
s-t orientations of planar graphs.
 
02.12.2014
Andrzej Dorobisz
Treewidth.
 
25.11.2014
18.11.2014,Patryk Mikos
Kernelization and Linear Programming Techniques
 
03.06.2014
M. Solon, P. Wójcik
Polynomial coloring of 3-colorable graphs.
 
27.05.2014
20.05.2014
13.05.2014
Adam Gągol
Constraint Satisfaction, Packet Routing, and the Lovász Local Lemma (by Harris and Srinivasan)

 
References:
David G. Harris, Aravind Srinivasan, Constraint Satisfaction, Packet Routing, and the Lovász Local Lemma, STOC '13

15.04.2014
Grzegorz Gutowski, Jakub Kozik
Lower bounds for on-line graph colorings (cont.)
(join work with P. Micek and X. Zhu)  
08.04.2014
01.04.2014,
Cancelled (all participants are invited to the lecture of prof. A. Ruciński.)
 
18.03.2014
Grzegorz Gutowski, Jakub Kozik
Lower bounds for on-line graph colorings
(join work with P. Micek and X. Zhu)  
04.03.2014
Igor Adamski
Outer-string graphs are chi-bounded
 
References:
Alexandre Rok, Bartosz Walczak, Outer-string graphs are chi-bounded, preprint
21.01.2014
Maciej Solon
On the number of edges in families of pseudo-discs
 
References:
Piotr Micek, Rom Pinchasi, On the number of edges in families of pseudo-discs, preprint
14.01.2014
Maciej Bendkowski
List Colouring When The Chromatic Number Is Close To the Order Of The Graph
 
References:
B. Reed, B. Sudakov, List Colouring When The Chromatic Number Is Close To the Order Of The Graph, Combinatorica December 2004, Volume 25, Issue 1, pp 117-123
07.01.2014
Aneta Pawłowska
Three Topics in Online List Coloring
 
References:
J. Carraher, S. Loeb, T. Mahoney, G. Puleo, M. Tsai, D.B. West,Three Topics in Online List Coloring, preprint
17.12.2013
10.12.2013,Damian Królik
Sum-paintability of generalized theta-graphs
 
References:
J. Carraher, T. Mahoney, G.J. Puleo, D.B. West , Sum-paintability of generalized theta-graphs, preprint
26.11.2013
Wojciech Łopata
Conflict-Free Colourings of Uniform Hypergraphs With Few Edges
 
References:
A.V. Kostochka, M. Kumbhat, T. Łuczak, Conflict-Free Colourings of Uniform Hypergraphs With Few Edges, Combinatorics, Probability and Computing Volume 21 Issue 4, July 2012
12.11.2013
Tomasz Krawczyk, Bartosz Walczak
Coloring subtree overlap graphs with O(log lgo n) colors.
 
05.11.2013
Grzegorz Guśpiel
On the construction of 3-chromatic hypergraphs with few edges.
 
References:
Heidi Gebauer, On the construction of 3-chromatic hypergraphs with few edges, JCTA 120 (2013)