**17. 5., 24. 5. 2011** (úterý [Tuesday], **8:30,
MFF UK Malá
Strana, S6**)

**Dániel Marx and Igor Razgon: Fixed-parameter
tractability of multicut parameterized by the size of the cutset.** STOC
2011.

(referuje Dušan Knop)

**Abstract:** Given an undirected graph $G$, a collection
$\{(s_1,t_1),..., (s_k,t_k)\}$ of
pairs of vertices, and an integer $p$, the Edge Multicut problem ask if
there
is a set $S$ of at most $p$ edges such that the removal of $S$
disconnects
every $s_i$ from the corresponding $t_i$. Vertex Multicut is the
analogous
problem where $S$ is a set of at most $p$ vertices. Our main result is
that
both problems can be solved in time $2^{O(p^3)}... n^{O(1)}$, i.e.,
fixed-parameter tractable parameterized by the size $p$ of the cutset
in the
solution. By contrast, it is unlikely that an algorithm with running
time of
the form $f(p)... n^{O(1)}$ exists for the directed version of the
problem, as
we show it to be W[1]-hard parameterized by the size of the cutset.

**3. 5., 10. 5. 2011** (úterý [Tuesday], **8:30,
MFF UK Malá
Strana, S6**)

**Friedrich Eisenbrand, Dömötör Pálvölgyi, and Thomas
Rothvoss:
Bin Packing via Discrepancy of Permutations. **SODA
2011.

(referuje Tomáš Dzetkulič)

The three-permutations-conjecture of Beck is the following. Given any 3 permutations on n symbols, one can color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols differs only by a constant. Beck's conjecture is well known in the field of discrepancy theory.

We establish a surprising connection between bin packing and Beck's conjecture: If the latter holds true, then the additive integrality gap of the 3-partition linear programming relaxation is bounded by a constant.

**19. 4., 26. 4. 2011** (úterý [Tuesday], **8:30,
MFF UK Malá
Strana, S6**)

**Ola Svensson: Santa
Claus Schedules Jobs on Unrelated Machines. **STOC 2010.

(referuje Marek Krčál)

**12. 4. 2011** (úterý [Tuesday], **8:30,
MFF UK Malá
Strana, S6**)

(referuje Vojtěch Bardejovský)

**29. 3., 5. 4. 2011** (úterý [Tuesday], **8:30,
MFF UK Malá
Strana, S6**)

**Georg Gottlob,
Reinhard Pichler,
Fang Wei:
Monadic datalog over
finite structures of bounded treewidth.**
ACM Trans. Comput. Log. 12(1): 3 (2010)

(referuje Martin Koutecký)

**15. 3., 22.3. 2011** (úterý [Tuesday], **8:30,
MFF UK Malá
Strana, S6**)

**Kevin P. Costello, Asaf Shapira, and Prasad Tetali: Randomized greedy: new variants of some classic
approximation algorithms. **SODA 2011.

(referuje Ondřej Zajíček)

1. Johnson’s approximation algorithm for MAX-SAT is one of the first approximation algorithms to be rigorously analyzed. It has been shown that the performance ratio of this algorithm is 2/3. We show that when executed on a random permutation of the variables, the performance ratio of this algorithm is improved to 2/3 + c for some c > 0 This resolves an open problem of Chen, Friesen and Zhang [JCSS 1999]. (See also the paper by Poloczek and Schnitger in these proceedings for related results on this algorithm and its variants).

2. Motivated by the above improvement, we consider the performance of the greedy algorithm for MAXCUT whose performance ratio is 1/2. Our hope was that running the greedy algorithm on a random permutation of the vertices would result in a 1/2 + c approximation algorithm. However, it turns out that in this case the performance of the algorithm remains 1/2. This resolves an open problem of Mathieu and Schudy [SODA 2008].

**1. 3., 8. 3. 2011** (úterý [Tuesday], **8:30,
MFF UK Malá
Strana, S6**)

**Davide Bilo, Luciano Guala and Guido Proietti: Improved
approximability
and
non-approximability
results
for
graph
diameter
decreasing
problems.** MFCS 2010.

(referuje Petr Kolman)