Seminář z aproximačních a online algoritmů

Petr Kolman, Jiří Sgall

Předchozí program semináře, zimní semestr 2011 [Previous program, Fall 2011]

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).

Abstract: We develop an optimal approximation algorithm for Maximum coverage over a matroid constraint. In contrast to the celebrated algorithm by Vondrák et al., our approach is entirely combinatorial. Both the greedy algorithm and naive local search give only a 1/2 approximation in our setting. However, by using an auxiliary objective function giving more weight to elements covered more than once, we are able to recover a local search algorithm which gives a 1-1/e approximation. We are currently working on generalizing the approach to monotone submodular maximization over a matroid constraint.

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.

19. 10., 26. 10. 2011 (středa [Wednesday], 12:20, MFF UK Malá Strana, S6)
Petr Kolman: Approximate Duality of Multicommodity  Multiroute Flows and Cuts: Single Source Case. SODA 2012.
(joint work with Christian Scheideler)

Abstract: Given an integer $h$, a graph $G=(V,E)$ with arbitrary positive edge capacities and $k$ pairs of vertices $(s_1,t_1), (s_2,t_2), \ldots, (s_k,t_k)$, called terminals, an $h$-route cut is a set $F\subseteq E$ of edges such that after the removal of the edges in $F$ no pair $s_i-t_i$ is connected by $h$ edge-disjoint paths (i.e., the connectivity of every $s_i-t_i$ pair is at most $h-1$ in $(V,E\setminus F)$). The $h$-route cut is a natural generalization of the classical cut problem for multicommodity flows (take $h=1$). The main result of this paper is an $O(h^5 2^{2h}(h+\log k)^2)$-approximation algorithm for the minimum $h$-route cut problem in the case that $s_1=s_2=\cdots=s_k$, called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems.

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

Lukasz Jez: Online Packet Scheduling

Abstract: I will present an overview of my Ph.D. thesis that concerns some online packet scheduling problems, namely the "Buffer Management with
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.