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

Petr Kolman, Jiří Sgall

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

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₁, ..., E_k} such that E_i is a multiway cut for commodity i and the maximum load on any edge is minimized. The load on an edge is defined to be the number of cuts in the solution containing the edge. In the capacitated version of the problem the goal is to minimize the maximum relative load on any edge---the ratio of the edge's load to its capacity. Multiway cut packing arises in the context of graph labeling problems where we are given a partial labeling of a set of items and a neighborhood structure over them, and the goal, informally stated, is to complete the labeling in the most consistent way. This problem was introduced by Rabani, Schulman, and Swamy (SODA'08), who developed an O(log n/log log n) approximation for it in general graphs, as well as an improved O(log² k) approximation in trees. Here n is the number of nodes in the graph. We present the first constant factor approximation for this problem in arbitrary undirected graphs. Our LP-rounding-based algorithm guarantees a maximum edge load of at most 8OPT + 4 in general graphs. Our approach is based on the observation that every instance of the problem admits a laminar solution (that is, no pair of cuts in the solution crosses) that is near-optimal.

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)

Abstract: In this paper we consider both the maximization variant MaxRep and the minimization variant MinRep of the famous Label Cover problem, for which, till now, the best approximation ratios known were O(\sqrt{n}). In fact, several recent papers reduced Label Cover to other problems, arguing that if better approximation algorithms for their problems existed, then a o(\sqrt{n})-approximation algorithm for Label Cover would exist. We show, in fact, that there are a O(n^{1/3})-approximation algorithm for MaxRep and a O(n^{1/3} log^{2/3}n)-approximation algorithm for MinRep. In addition, we also exhibit a randomized reduction from Densest k-Subgraph to Max Rep, showing that any approximation factor for MaxRep implies the same factor (up to a constant) for Densest k-Subgraph.

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)

Abstract: We consider the problem of collecting weighted items from a dynamic queue S. Before each step, some items at the front of S can be deleted and some other items can be added to S at any place. An item, once deleted, cannot be re-inserted, in other words, it "expires". We are allowed to collect one item from S per step. Each item can be collected only once. The objective is to maximize the total weight of the collected items. We study the online version of the dynamic queue problem. It is quite easy to see that the greedy algorithm that always collects the maximum-value item is 2-competitive, and that no deterministic online algorithm can be better than 1:618-competitive. We improve both bounds: We give a 1:89-competitive algorithm for general dynamic queues and we show a lower bound of 1:632 on the competitive ratio. We also provide other upper and lower bounds for restricted versions of this problem. The dynamic queue problem is a generalization of the well-studied buffer management problem, and it is an abstraction of the buffer management problem for network links with intermittent access.

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)

Abstract: In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time O(mn), dates back to König’s work in 1916. The currently most efficient algorithm takes time O(m), and is due to Cole, Ost, and Schirra. We improve this running time to O(min{m, n^2.5 ln(n)/ d }); this minimum can never be larger than O(n^1.75\sqrt{ln n}). We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a d-regular bipartite graph independently with a probability p = O( n ln n / d^2 ) then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to non-existence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger’s sampling theorem for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the O(m\sqrt{n}) algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to poly-logarithmic factors (in fact, up to ln^2 n).

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)

Abstract: One of the main subjects of this lecture are fair edge deletion problems. In edge deletion problems, we are given a graph $G$ and a graph property $\pi$ and the task is to find a subset of edges the deletion of which results in a subgraph of $G$ satisfying the property $\pi$. Typically the objective is to minimize the total number of deleted edges while in less common fair versions the objective is to minimize the maximum number of edges removed from a single vertex. Both classes of edge deletion problems contain many NP-hard problems (e.g., max-cut for the classical version, $(\ell,k)$-coloring or matching cut problems, for the fair version).

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.