**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*(*n*^{6}EO 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*
((*n*^{4}EO+*n*^{5})log *nM*) time. The
strongly polynomial version of this faster algorithm runs in *O*((*n*^{5}EO
+ *n*^{6}) 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).