**5. 1. 2015 **(pondělí [Monday], 10:40, MFF UK Malá Strana
S8)

**Martin Koutecký: Extended Formulation for Binary CSP that is
Compact for Instances of Bounded Treewidth**

**15. 12. 2014 **(pondělí [Monday], 10:40, MFF UK Malá Strana
S8)

**Anna R. Karlin, Claire Kenyon, Dana Randall: ****Dynamic
TCP Acknowledgment and Other Stories about e/(e-1)****.**
Algorithmica 36(3): 209-224 (2003)

(referuje Lukáš Folwarczný)

**Abstract:** We present the first optimal randomized online
algorithms for the TCP acknowledgment problem [5] and the Bahncard
problem [7]. These problems are well-known to be generalizations
of the classical online ski rental problem, however, they appeared
to be harder. In this paper, we demonstrate that a number of
online algorithms which have optimal competitive ratios of

**1. 12., 8. 12. 2014 **(pondělí [Monday], 10:40, MFF UK Malá
Strana S8)

**Reuven Bar-Yehuda, Dror Rawitz: On the Equivalence
Between the Primal-Dual Schema and the Local Ratio Technique.
**SIAM J. Discrete Math., 19(3), 762–797.

(referuje Pavel Veselý)

**24. 11. 2014 **(pondělí [Monday], 10:40, MFF UK Malá Strana
S8)

**Dor Arad, Yael Mordechai, Hadas Shachnai: Tighter Bounds for
Makespan Minimization on Unrelated Machines.** http://arxiv.org/abs/1405.2530.

(referuje Martin Böhm)

**Abstract: **We consider the problem of scheduling *n* jobs to minimize the
makespan on *m* unrelated machines, where job *j*
requires time *p_ij**i*. A classic algorithm of Lenstra
et al. yields the best known approximation ratio of 2 for the
problem. Improving this bound has been a prominent open problem
for over two decades. In this paper we obtain a tighter bound for
a wide subclass of instances which can be identified efficiently.
Specifically, we define the feasibility factor of a given instance
as the minimum fraction of machines on which each job can be
processed. We show that there is a polynomial-time algorithm that,
given values *L* and *T*, and an instance
having a sufficiently large feasibility factor* h*\in(0,1],
either proves that no schedule of mean machine completion time *L
*and makespan *T* exists, or else finds a schedule of
makespan at most *T+L/h<2T*. For the restricted version
of the problem, where for each job *j* and machine *i,
p_ij*\in{*p_j*,\infty}, we show that a simpler algorithm
yields a better bound, thus improving for highly feasible
instances the best known ratio of 33/17+eps, for any fixed
eps>0, due to Svensson.

**10. 11. 2014 **(pondělí [Monday], 10:40, MFF UK Malá Strana
S8)

**Martin Skutella: A note on the ring loading problem.** SODA
2015. Also http://arxiv.org/abs/1405.0789.

(referuje Karel Král)

**Abstract:** The Ring Loading Problem is an optimal routing
problem arising in the planning of optical communication networks
which use bidirectional SONET rings. In mathematical terms, it is
an unsplittable multicommodity flow problem on undirected ring
networks. We prove that any split routing solution to the Ring
Loading Problem can be turned into an unsplittable solution while
increasing the load on any edge of the ring by no more than
+(19/14)D, where D is the maximum demand value. This improves upon
a classical result of Schrijver, Seymour, and Winkler (1998) who
obtained a slightly larger bound of +(3/2)D. We also present an
improved lower bound of +1.1 D (previously +1.01 D) on the best
possible bound and disprove a famous long-standing conjecture of
Schrijver et al. in this context.

**3. 11. 2014 **(pondělí [Monday], 10:40, MFF UK Malá Strana
S8)

**Achlioptas, D., Chrobak, M., Noga, J.: Competitive analysis
of randomized paging algorithms. **Theoretical Computer
Science 234, 203–218 (2000)(referuje Lukáš Folwarczný)

**Abstract:** In this paper we use competitive analysis to
study the performance of randomized on-line paging algorithms. Our
goal is to show how the concept of work functions, used previously
mostly for the analysis of deterministic algorithms, can also be
applied, in a systematic fashion, to the randomized case. We
provide a new, H_k-competitive algorithm for paging. Our
algorithm, as well as its analysis, is simpler than the known
algorithm by McGeoch and Sleator. Another advantage of our
algorithm is that it can be implemented with complexity bounds
independent of the number of past requests: O(k^2 log k) memory and O(k^2) time
per request.

**20. 10. 2014** (pondělí [Monday], 10:40, MFF UK Malá Strana
S8)

**Dušan Knop: Parameterized hardness for length-bounded cuts.**

**Abstract:** I would like to present a parametrized result
about length bounded cuts, namely that finding an optimal length
bounded cut is W[1]-hard when parameterized by path-width only. I
will aslo talk a little bit about some lower bound consequences
(assuming ETH). I may also sketch some of our algorithmic results.
For example an O(n^k) time algorithm where k is the tree-width and
O(f(k) n) time algorithm where k is the size of vertex-cover of
the input graph.

**13. 10. 2014** (pondělí [Monday], 10:40, MFF UK Malá Strana
S8)

**Martin Koutecký: The length bounded cut polytope for
series-parallel graphs.**

(joint work with Petr Kolman)

**Abstract:** Given a graph $G=(V,E)$ with two distinguished
vertices $s,t\in V$ and an integer parameter $L$, an {\em
$L$-bounded cut} is a subset $F$ of edges such that the every path
between $s$ and $t$ in $(V,E\set minus F)$ has length at least
$L$. The minimum $L$-bounded cut problem is to find an $L$-bounded
cut of minimum cardinality.

The problem was first studied around 1970 but still, the problem
is not much understood. It is known that the problem is NP-hard
and that even finding a 1.1377 approximation is NP-hard. On the
other hand, the best known approximation algorithm has
approximation ratio, in terms of $n$, only $\Theta(n^{2/3})$. For
series-parallel graphs the problem is solvable in polynomial time
but the only linear programming relaxation that we are aware of
has integrality gap $\Theta(\sqrt{n})$.

We propose and examine a new LP-relaxation (of polynomial size) of
the $L$-bounded cut problem and show that all vertices of the
associated polytope are integral if the input graph is a
series-parallel graph.

**6. 10. 2014** (pondělí [Monday], 10:40, MFF UK Malá Strana
S8)

**Jiří Sgall: Online Competitive Algorithms for Multi-Level
Aggregation with Deadlines.**

(joint work with Marek Chrobak, Lukáš Folwarczny, and Pavel
Veselý)

**Abstract:** In the Multi-Level Aggregation Problem
(MLAPD), requests arrive at the leaves of a weighted tree T each
with its own deadline. A service is defined as an arbitrary
subtree X of T. This subtree X services all requests that are
pending in the nodes of X at the cost equal to the total weight of
X. The objective is to minimize the cost of all service sub-trees
while keeping all the deadlines. We study online algorithms for
MLAPD. For trees of height H we give an online algorithm with
competitive ratio 2^O(H).