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

Petr Kolman, Jiří Sgall

Předchozí program semináře, letní semestr 2006 [Previous program, Spring 2006]

10. 5., 24. 5. 2006 (středa [Wednesday], 9.00, MFF UK Malá Strana S8)

Moses Charikar, Konstantin Makarychev and Yury Makarychev:
Directed Metrics and Directed Graph Partitioning Problems. SODA 2006
(referuje Petr Kučera)

Abstract:  The theory of embeddings of finite metrics has provided a powerful toolkit for graph partitioning problems in undirected graphs. The connection comes from the fact that the integrality gaps of mathematical programming relaxations for sparsest cut in undirected graphs is exactly equal to the minimum distortion required to embed certain metrics into l1. No analog of this metric embedding theory exists for directed (asymmetric) metrics, the natural distance functions that arise in considering mathematical relaxations for directed graph partioning problems. We initiate a study of metric embeddings for directed metrics, motivated by understanding directed variants of sparsest cut.It turns out that there are two different ways to formulate sparsest cut in directed graphs (depending on whether one insists on partitioning the graph into two pieces or not). Different subclasses of directed metrics arise in the consideration of mathematical relaxations for these two formulations and the embedding questions that result are quite different. Unlike in the undirected case, where the natural host space is l1, the host space in the directed case is not obvious and depends on the problem formulation. Our work is a first step at understanding this space of directed metrics, the resulting embedding questions and their relationships to directed graph partitioning problems.

12. 4., 3. 5. 2006 (středa [Wednesday], 9.00, MFF UK Malá Strana S8)

Tomáš Ebenlendr: An optimal algorithm for online scheduling on uniformly related machines
(joint work with Wojtek Jawor and Jiří Sgall)

Abstract: We consider preemptive scheduling on uniformly related machines when jobs arrive one by one with the objective to minimize makespan.  We give an optimal online algorithm in the setting where jobs arrive one by one. While this algorithm is deterministic, it is shown that it is optimal even among all randomized algorithms. Furthermore, this algorithm is optimal for any fixed combination of speeds of the machines. We show that the overall competitive ratio of this algorithm is between 2.05 and $e\approx 2.71$.

29. 3., 5. 4. 2006 (středa [Wednesday], 9.00, MFF UK Malá Strana S8)

Günter Rote: Pursuit-Evasion with Imprecise Target Location. SODA 2003.
(referuje Ondřej Zajíček)

Abstract: We consider a game between two persons where one person tries to chase the other, but the pursuer only knows an approximation of the true position of the fleeing person. The two players have identical constraints on their speed. It turns out that the fugitive can increase his distance from the pursuer beyond any limit. However, when the speed constraints are given by a polyhedral metric, the pursuer can always remain within a constant distance of the other person.We apply this problem to buffer minimization in an online scheduling problem with conflicts.

15. 3., 22. 3. 2006 (středa [Wednesday], 9.00, MFF UK Malá Strana S8)

M. Andrews, J. Chuzhoy, S. Khanna and L. Zhang. Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. FOCS 2005. Also available here.
J. Chuzhoy and S. Khanna. New Hardness Results for Undirected Edge-Disjoint Paths. Manuscript, 2005.
(referuje Petr Kučera)

Abstract: In the Edge-Disjoint Paths problem with Congestion (EDPwC), we are given a graph with n nodes, a set of terminal pairs and an integer c. The objective is to route as many terminal pairs as possible, subject to the constraint that at most c demands can be routed through any edge in the graph. When c = 1, the problem is simply referred to as the Edge-Disjoint Paths (EDP) problem. In this paper, we study the hardness of EDPwC in undirected graphs. We obtain an improved hardness result for EDP, and also show the first polylogarithmic integrality gaps and hardness of approximation results for EDPwC. Specifically, we prove that EDP is (\log ^{\frac{1}{2} - {\rm E}} n)-hard to approximate for any constant \varepsilon > 0, unless NP \subseteq ZPTIME(n^{poly\log n} ).We also show that for any congestion c = o(log log n/ log log log n), there is no (Log^{\frac{{1 - 5}}{{c + 1}}} n) approximation algorithm for EDPwC, unless NP\subseteqZPTIME(npolylog n).For larger congestion, where c = o(log log n/ log log log n) for some constant n, we obtain superconstant inapproximability ratios. All of our hardness results can be converted into integrality gaps for the multicommodity flow relaxation. We also present a separate elementary direct proof of this integrality gap result. Finally, we note that similar results can be obtained for the All-or-Nothing Flow (ANF) problem, a relaxation of EDP, in which the flow unit routed between the source-sink pairs does not have follow a single path, so the resulting flow is not necessarily integral. Using standard transformations, our results also extend to the node-disjoint versions of these problems as well as to the directed setting.

8. 3. 2006 (středa [Wednesday], 9.00, MFF UK Malá Strana S8)

Mike Paterson and Uri Zwick: Overhang. SODA 2006.
(referuje Tomáš Ebenlendr)
Pezentace autorů: http://www.cs.tau.ac.il/~zwick/slides/overhang.pps

Abstract: How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of 1/2Hn, where Hn = Σni=1 1/i ~ ln n is the nth harmonic number, by stacking all the blocks one on top of another with the ith block from the top displaced by 1/2i beyond the block below. This solution is widely believed to be optimal. We show that it is exponentially far from optimal by giving explicit constructions with an overhang of Ω(n1/3). We also prove some upper bounds on the overhang that can be achieved. The stability of a given stack of blocks corresponds to the feasibility of a linear program and so can be efficiently determined.

1. 3. 2006 (středa [Wednesday], 9.00, MFF UK Malá Strana S8)

Petr Kolman:
Reversal Distance for Strings with Duplicates: Linear Time Approximation using Suffix Trees
(joint work with Tomasz Waleń)

Abstract: In the last decade there has been an ongoing interest in string comparison problems; to large extend the interest was stimulated by genome rearrangement problems in computational biology but related problems appear in many other areas of computer science. A particular attention was given to the problem of {\em sorting by reversals} ({\SBR}): given two strings, $A$ and $B$, find the minimum number of reversals that transform the string $A$ into the string $B$ (a {\em reversal} $\rho(i,j)$, $i<j$, transforms a string $A=a_1\ldots a_n$ into a string $A'=a_1\ldots a_{i-1} a_{j} a_{j-1} \ldots a_{i} a_{j+1} \ldots a_n$).

Most of the time the problem was studied for strings in which every symbol appears exactly once (that is, for permutations) and only recently attention was given to the general case where duplicates of the symbols are allowed. In this talk we consider the problem $k$-{\SBR}, a version of {\SBR} in which each symbol is allowed to appear up to $k$ times in each string, for some $k\geq 1$. The main result is a $\Theta(k)$-approximation algorithm for $k$-{\SBR} running in time $O(n)$; compared to the previously known algorithm for $k$-{\SBR}, this is by a factor of $\Theta(k)$ better approximation ratio and by a factor of $\Theta(k)$ faster running time.  A crucial ingredient of our algorithm is the data structure known as suffix tree.