**14. 12. 2011, 11. 1. 2012** (středa [Wednesday], **12:20,
MFF UK Malá Strana, S6**)

**Anke van Zuylen: Simpler
3/4-approximation algorithms for MAX SAT. **WAOA 2011.

(referuje Lukáš Mach)

**Abstract:** We consider the recent randomized
3/4-approximation algorithm for MAX
SAT of Poloczek and Schnitger. We give a much simpler set of
probabilities for setting the variables to true or false, which
achieve
the same expected performance guarantee. Our algorithm suggests a
conceptually simple way to get a deterministic algorithm: rather
than
comparing to an unknown optimal solution, we instead compare the
algorithm's output to the optimal solution of an LP relaxation.
This
gives rise to a new LP rounding algorithm, which also achieves a
performance guarantee of 3/4.

**7. 12. 2011, 4. 1. 2012** (středa [Wednesday], **12:20, MFF
UK Malá Strana, S6**)

**Joachim Kneis, Alexander Langer, Peter Rossmanith: Courcelle's Theorem - A
Game-Theoretic Approach**.

(referuje Martin Koutecký)

**Abstract:** Courcelle's Theorem states that every problem
definable in Monadic Second-Order logic can be solved in linear
time on structures of bounded treewidth, for example, by
constructing a tree automaton that recognizes or rejects a tree
decomposition of the structure. Existing, optimized software like
the MONA tool can be used to build the corresponding tree
automata, which for bounded treewidth are of constant size.
Unfortunately, the constants involved can become extremely large -
every quantifier alternation requires a power set construction for
the automaton. Here, the required space can become a problem in
practical applications. In this paper, we present a novel, direct
approach based on model checking games, which avoids the expensive
power set construction. Experiments with an implementation are
promising, and we can solve problems on graphs where the
automata-theoretic approach fails in practice.

**23. 11., 30. 11. 2011** (středa [Wednesday], **12:20, MFF
UK Malá Strana, S6**)

**Tobias Moemke and Ola Svensson: Approximating Graphic
TSP by Matchings. **FOCS 2011.

(referuje Ondřej Bílka)

**Abstract:** We present a framework for approximating the
metric TSP based on a novel use of matchings. Traditionally,
matchings have been used to add edges in order to make a given
graph Eulerian, whereas our approach also allows for the removal
of certain edges leading to a decreased cost. For the TSP on
graphic metrics (graph-TSP), the approach yields a
1.461-approximation algorithm with respect to the Held-Karp lower
bound. For graph-TSP restricted to a class of graphs that contains
degree three bounded and claw-free graphs, we show that the
integrality gap of the Held-Karp relaxation matches the
conjectured ratio 4/3. The framework allows for generalizations in
a natural way and also leads to a 1.586-approximation algorithm
for the traveling salesman path problem on graphic metrics where
the start and end vertices are prespecified.

**16. 11. 2011** (středa [Wednesday], **12:20, MFF UK Malá
Strana, S6**)

**Yuval Filmus: Maximum
coverage over a matroid using local search
** Joint work with Justin Ward (U. of Toronto).

**2. 11., 9. 11. 2011** (středa [Wednesday], **12:20, MFF UK
Malá Strana, S6**)

**Chandra Chekuri, Bruce Shepherd, and Christophe Weibel: Flow-Cut
Gaps for Integer and Fractional Multiflows.** SODA 2010.
Also available at http://arxiv.org/abs/1008.2136.

(referuje Dušan Knop)

**Abstract: **Consider a routing problem consisting of a
demand graph H and a supply graph G. If the pair obeys the cut
condition, then the flow-cut gap for this instance is the minimum
value C such that there is a feasible multiflow for H if each edge
of G is given capacity C. The flow-cut gap can be greater than 1
even when G is the (series-parallel) graph K_{2,3}. In this paper
we are primarily interested in the "integer" flow-cut gap. What is
the minimum value C such that there is a feasible integer valued
multiflow for H if each edge of G is given capacity C? We
conjecture that the integer flow-cut gap is quantitatively related
to the fractional flow-cut gap. This strengthens the well-known
conjecture that the flow-cut gap in planar and minor-free graphs
is O(1) to suggest that the integer flow-cut gap is O(1). We give
several results on non-trivial special classes of graphs
supporting this conjecture and further explore the "primal" method
for understanding flow-cut gaps. Our results include:

- Let G be obtained by series-parallel operations starting from an
edge st, and consider orienting all edges in G in the direction
from s to t. A demand is compliant if its endpoints are joined by
a directed path in the resulting oriented graph. If the cut
condition holds for a compliant instance and G+H is Eulerian, then
an integral routing of H exists.

- The integer flow-cut gap in series-parallel graphs is 5. We also
give an explicit class of instances that shows via elementary
calculations that the flow-cut gap in series-parallel graphs is at
least 2-o(1); this simplifies the proof by Lee and Raghavendra.

- The integer flow-cut gap in k-Outerplanar graphs is c^{O(k)} for
some fixed constant c.

- A simple proof that the flow-cut gap is O(\log k^*) where k^* is
the size of a node-cover in H; this was previously shown by
G\"unl\"uk via a more intricate proof.

(joint work with Christian Scheideler)

Abstract:

**Lukasz Jez: Online Packet Scheduling**

Bounded Delay" (BMwBD) problem and some of its generalizations. The BMwBD problem is in fact a time-online variant of a rather simple job scheduling problem: weighted throughput maximization of unit-size jobs on a single machine, where the jobs have integer release times and deadlines (discrete time flow is assumed in all these problems), and real-valued weights. In the first generalization of BMwBD that we consider the algorithm does not know exact deadlines of the jobs/packets but rather only their relative order---such limited knowledge is sufficient for some simple algorithms for BMwBD that have been considered in the literature. In the other generalization we allow arbitrary integer sizes of the jobs/packets and preemption, i.e., one unit of a job is processed per time step, units of different jobs can be interwoven but the weight of a job is awarded to the algorithm only if it processes all the job's units before its deadline. We focus on randomized algorithms for BMwBD and deterministic ones for the generalized problems.