Seminar on Approximation and Online Algorithms

**3. 11., 27. 10. 2017** (pátek [Friday], 10:40, MFF UK Malá Strana
S6)

**Syamantak Das and Andreas Wiese: On
minimizing the makespan when some jobs cannot be assigned on
the same machine.** ESA 2017.

(presented by Jan Voborník)

**13. 10., 20. 10. 2017** (pátek [Friday], 10:40, MFF UK Malá
Strana S6)

**Pavel Veselý: Parameterized Approximation Schemes for Steiner
Trees with Small Number of Steiner Vertices **

(joint work with Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop,
Tomáš Masařík, and Tomáš Toufar)

**Abstract: **We study the Steiner Tree problem, in which a
set of terminal vertices needs to be connected in the cheapest
possible way in an edge-weighted graph. This probl em has been
extensively studied from the viewpoint of approximation and also
parametrization. In particular, on one hand Steiner Tree is known
to be APX- hard, and W[2]-hard on the other, if parameterized by
the number of non-terminals (Steiner vertices) in the optimum
solution. In contrast to this we give an efficient parameterized
approximation scheme (EPAS), which circumvents both hardness
results. Moreover, our methods imply the existence of a polynomial
size approximate kernelization scheme (PSAKS) for the assumed p
arameter.

We further study the parameterized approximability of other
variants of Steiner Tree, such as Directed Steiner Tree and
Steiner Forest. For neither of these an EPTAS is likely to exist
for the studied parameter: for Steiner Forest an easy observation
shows that the problem is APX-hard, even if the input graph
contains no Steiner vertices. For Directed Steiner Tree we prove
that computing a constant approximation for this parameter is
W[1]- hard. Nevertheless, we show that an EPAS exists for
Unweighted Directed Steiner Tree. Also we prove that there is an
EPAS and a PSAKS for Steiner Forest if in addition to the number
of Steiner vertices, the number of connected components of an
optimal solution is considered to be a parameter.

**6. 10., 13. 10. 2017** (pátek [Friday], 10:40, MFF UK Malá
Strana S6)

**Petr Kolman: The length bounded cut problem
**

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

The early research on the problem was motivated by an effort to
generalize the Max Flow - Min Cut theorem to flows of bounded
lenght (i.e., flows decomposable into paths of bounded length).
Another motivation for studying the problem were military
applications: the goal was to disrupt the movements of enemy
troops and material in a capacitated supply network. Later, the
problem was also studied in the context of communication networks
where the length of paths is often an issue.

Though the problem is very simple to state and has been studied
since the beginning of the 70's, it is not much understood yet. 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 for general graphs has approximation
ratio, in terms of $n$, only $\Theta(n^{2/3})$.