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

Petr Kolman, Jiří Sgall

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

20. 5. 2009 (středa [Wednesday], 10:40, MFF UK Malá Strana, posluchárna S9)

Satoru Iwata and James B. Orlin: A Simple Combinatorial Algorithm for Submodular Function Minimization. SODA 2009.
(referuje Tomáš Ebenlendr)

Abstract: This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n6EO log nM) time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function evaluation. The algorithm can be improved to run in O ((n4EO+n5)log nM) time. The strongly polynomial version of this faster algorithm runs in O((n5EO + n6) log n) time for real valued general submodular functions. These are comparable to the best known running time bounds for submodular function minimization. The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method.

29. 4., 6. 5. 2009 (středa [Wednesday], 10:40, MFF UK Malá Strana, posluchárna S9)

René A. Sitters: Approximability of Average Completion Time Scheduling on Unrelated Machines. ESA 2008.
(referuje Marek Krčál a Jiří Sgall)

Abstract: We show that minimizing the sum of completion times on unrelated machines is APX-hard if preemption of jobs is allowed. Additionally, we show that randomized rounding of a convex quadratic program gives a non-preemptive schedule for which the sum of weighted completion times is less than 1.81 times the optimal preemptive sum. This factor is 2.78 if release dates are involved. We sketch how the ratios can be reduced further.

15. 4., 22.4. 2009 (středa [Wednesday], 10:40, MFF UK Malá Strana, posluchárna S9)

Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, and Mohammad R. Salavatipour:
A Logarithmic Approximation for Unsplittable Flow on Line Graphs.
SODA 2009.
(referuje Petr Kolman)

Abstract: We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time s_i, an end time t_i, a demand d_i > 0, and a profit p_i > 0. A task, if accepted, requires d_i units of “bandwidth” from time s_i to t_i and accrues a profit of p_i. For every time t, we are also specified the available bandwidth c_t, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. In this paper, we present the first polynomial-time O(log n)-approximation algorithm for this problem. No polynomial-time o(n)-approximation was known prior to this work. Previous results for this problem were known only in more restrictive settings, in particular, either if the given instance satisfies the so-called “no-bottleneck” assumption: max_i di_ ≤ min_t c_t, or else if the ratio of the maximum to the minimum demands and ratio of the maximum to the minimum capacities are polynomially (or quasi-polynomially) bounded in n. Our result, on the other hand, does not require any of these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Omega(n) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

1. 4., 8. 4. 2009 (středa [Wednesday], 10:40, MFF UK Malá Strana, posluchárna S9)

C. Chekuri and S. Khanna. and F. Bruce Shepherd: A Note on Multiflows and Treewidth. Algorithmica, 2007.
(referuje Dušan Knop)

Abstract: We consider multicommodity flow problems in capacitated graphs where the treewidth of the underlying graph is bounded by r. The parameter r is allowed to be a function of the input size. An instance of the problem consists of a capacitated graph and a collection of terminal pairs. Each terminal pair has a non-negative demand that is to be routed between the nodes in the pair. A class of optimization problems is obtained
when the goal is to route a maximum number of the pairs in the graph subject to the capacity constraints on the edges. Depending on whether routings are fractional, integral or unsplittable, three different versions are obtained; these are commonly referred to respectively as maximum MCF, EDP (the demands are further constrained to be one) and UFP. We obtain several results for these problems.

18. 3. 2009 (středa [Wednesday], 10:40, MFF UK Malá Strana, posluchárna S9)

Michael R. Fellows, Jiong Guo, Hannes Moser, and Rolf Niedermeier: A Generalization of Nemhauser and Trotter's Local Optimization Theorem. STACS 2009.
(referuje Ondřej Zajíček)

Abstract: The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We present a framework that generalizes Nemhauser and Trotter’s result to vertex deletion and graph packing problems, introducing novel algorithmic strategies based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did).

We exhibit our framework using a generalization of Vertex Cover, called Bounded-Degree Deletion, that has promise to become an important tool in the analysis of gene and other biological networks. For some fixed d>=0, Bounded-Degree Deletion asks to delete as few vertices as possible from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d = 0. Our generalization of the Nemhauser-Trotter theorem implies that Bounded-Degree Deletion has a problem kernel with a linear number of vertices for every constant d. We also outline an application of our extremal combinatorial approach to the problem of packing stars with a bounded number of leaves. Finally, charting the border between (parameterized) tractability and intractability for Bounded-Degree Deletion, we provide a W[2]-hardness result for Bounded-Degree Deletion in case of unbounded d-values.

11. 3. 2009 (středa [Wednesday], 10:40, MFF UK Malá Strana, posluchárna S9)

Robert Elsässer, Thomas Sauerwald: Cover Time and Broadcast Time. STACS'09
(referuje Tomáš Ebenlendr)

Abstract: We introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs the intuition of Chandra et al. (1997) that ``the cover time of the graph is an appropriate metric for the performance of certain kinds of randomized broadcast algorithms''. Our bounds also demonstrate that the relationship between cover time and broadcast time is much stronger than the known relationships between any of them and the mixing time (or the closely related spectral gap).