**5. 1., 12. 1. 2010** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

**Siddharth Barman,
Shuchi Chawla:
Packing
multiway cuts in capacitated graphs.**
SODA 2009.

(referuje Tomáš Ebenlendr)

**Abstract: **We consider the following "multiway cut packing"
problem in undirected graphs: given a graph *G* = (*V, E*)
and *k*
commodities, each corresponding to a set of terminals located at
different vertices in the graph, our goal is to produce a collection of
cuts {*E*_{1}, ..., *E _{k}*} such that

**15. 12. 2009** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, chodba KAM 2. patro**)

**Łukasz Jeż: Randomized Packet Scheduling in Adaptive Adversary
Model**

(joint work with M. Bienkowski and M. Chrobak)

**Abstract: **In packet scheduling problem, packets with weights
and
deadlines arrive at a network switch over time, and the goal is to send
those packets on the outgoing link while maximizing the total weight of
the packets that are sent before their deadlines. Network traffic
obviously depends on the packet scheduling algorithm, but this
phenomenon is not captured in the typically assumed oblivious adversary
model. Another phenomenon that seemingly makes the analysis of
algorithms in this model difficult is the random nature of the
adversary's schedule. Because of that it is unclear whether it can be
assumed that the adversary's schedule is in earliest deadline first
order, and such assumption lies at the core of most upper bounds in the
oblivious adversary model.

Despite that we show that the RMix algorithm by Chin et al. remains
e/(e-1)-competitive, though its original analysis does not apply
directly to adaptive adversary model. On the other hand we improve the
5/4 lower bound (derived against oblivious adversary) to 4/3, and prove
that this is tight on 2-bounded instances. The lower bound construction
can be modified to give 6/5 and 4/3 lower bounds for both unrestricted
and memoryless scale-invariant algorithms on more restricted 2-uniform
instances.

**8. 12. 2009** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

**Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff:
Improved
Approximation Algorithms for Label Cover Problems.** ESA 2009.

(referuje Jiří Sgall)

**24. 11., 1. 12. 2009** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, chodba KAM 3. patro**)

**Peerapong Dhangwatnotai,
Shahar Dobzinski,
Shaddin Dughmi,
Tim Roughgarden:
Truthful
Approximation Schemes for Single-Parameter Agents.**
FOCS 2008.

(referuje Ondřej Zajíček)

**Abstract: **We present the first monotone randomized
polynomial-time approximation
scheme (PTAS) for minimizing the makespan of parallel related machines
(Q||C_{max}), the paradigmatic problem in single-parameter
algorithmic mechanism design. This result immediately gives a
polynomial-time, truthful (in expectation) mechanism whose
approximation guarantee attains the best-possible one for all
polynomial-time algorithms (assuming P not equal to NP). Our
algorithmic techniques are flexible and also yield, among other
results, a monotone deterministic quasi-PTAS for Q||C_{max} and
a monotone randomized PTAS for max-min scheduling on related machines.

**3. 11., 10. 11. 2009** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, S9**)

**Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde
Hurand, Artur Jeż, Łukasz Jeż, and Grzegorz Stachowiak:
Collecting
Weighted Items from a Dynamic Queue.** SODA 2009.

(referuje Milan Straka)

**20. 10., 27. 10. 2009** (úterý [Tuesday], **9:00,
MFF UK Malá
Strana, chodba KAM 3. patro
**

**Ashish
Goel, Michael Kapralov, and Sanjeev Khanna:
Perfect
Matchings via Uniform Sampling in Regular Bipartite Graphs.**
SODA
2009.

(referuje Dušan Knop)

**6. 10., 13. 10. 2009** (úterý [Tuesday], **9:00, MFF UK Malá
Strana, chodba KAM 3. patro**)

**Petr Kolman: Fair edge deletion problems on tree decomposable
graphs.**

(joint work with B. Lidický and J.-S. Sereni)

It is well known that many NP-hard problems become tractable when restricted to a certain class of graphs. The Monadic Second-Order Logic (MSOL) provides a rather general framework for dealing with NP-hard problems on graphs of bounded treewidth and other classes of tree-decomposable graphs. It has been shown not only that every problem expressible in MSOL can be solved in linear time but also that problems from several extension of MSOL are solvable in polynomial time, on tree-decomposable graphs. However, the fair edge deletion problems do not fit into these general frameworks.

We extend the previous work by Borie, Parker and Tovey, 1995, and describe a framework that provides a way to deal, in polynomial time on tree-decomposable graphs, with many of the fair edge deletion problems. In particular, we prove that if $\pi$ is a graph property expressible in MSOL, then the problem to find a set $F$ of edges such that the maximum degree in $(V,F)$ is as small as possible and the graph $(V,E\setminus F)$ satisfies $\pi$ is solvable in polynomial time.

We also describe a $\Theta(\sqrt{n})$ approximation algorithms for some of the fair edge deletion problems ($s$-$t$ cut and odd cycle transversal) for general graphs.