June 2, 2020 (úterý [Tuesday], 14:00, MFF UK Malá Strana, S8)
Andreas E. Feldmann: An Integral Linear Programming Relaxation
for Parameterized Steiner Trees
Abstract:We present a novel linear program (LP) for the
Steiner Tree problem, where a set of terminal vertices need to be
connected by a minimum weight tree in an edge-weighted graph. This
problem is NP-hard and, unless P=NP, therefore does not have an
efficiently computable polynomial-sized integral LP, for which the
optimum LP solution encodes an optimum Steiner tree. However,
Steiner Tree is fixed-parameter tractable when parameterized by
the number k of terminals, and can be solved in O(3^k |V| + 2^k
|V|^2) time via the Dreyfus-Wagner algorithm. We show that the
problem admits an integral LP with 3^k |E| variables and 2^k |V|
constraints. This improves on a previous result by Siebert et al.
[2018], who gave an integral LP of size O((2k/e)^k) |V|^O(1).
May 26, 2020 (úterý [Tuesday], 14:00, MFF UK Malá Strana, S8)
Petr Kolman: How
to Cut a Ball without Separating: Improved Approximations for
Length Bounded Cut.
Abstract: The Minimum Length Bounded Cut problem is a natural variant of Minimum Cut: given a graph, terminal nodes s, t and a parameter L, find a minimum cardinality set of nodes (other than s, t) whose removal ensures that the distance from s to t is greater than L. We focus on the approximability of the problem for bounded values of the parameter L. The problem is solvable in polynomial time for L ≤ 4 and NP-hard for L ≥ 5. The best known algorithms have approximation factor (L − 1)/2. It is NP-hard to approximate the problem within a factor of 1.7175 and Unique Games hard to approximate it within Ω(L), for any L ≥ 5. Moreover, for L = 5 the problem is 4/3 − ε Unique Games hard for any ε > 0.
Our first result matches the hardness for L = 5 with a
4/3-approximation algorithm for this case, improving over the
previous 2-approximation. For 6-bounded cuts we give a
7/4-approximation, improving over the previous best
3-approximation. More generally, we achieve approximation ratios
that always outperform the previous (L − 1)/2 guarantee for any
(fixed) value of L, while for large values of L, we achieve a
significantly better ((11/25)L + O(1))- approximation. All our
algorithms apply in the weighted setting, in both directed and
undirected graphs, as well as for edge-cuts, which easily reduce
to the node-cut variant. Moreover, by rounding the natural linear
programming relaxation, our algorithms also bound the
corresponding bounded-length flow-cut gaps.
Joint work with Eden Chlamtáč.
March 3, 2020 (úterý [Tuesday], 14:00, MFF UK Malá Strana, S8)
Cornelius Brand: An Algorithmic Method of Partial Derivatives
Abstract: Polynomial identity testing is one of the most central problems in complexity theory and has a host of combinatorial applications. It is formulated as follows: Given a "succinct" representation of a multivariate polynomial (usually through so-called arithmetic circuits), decide whether the polynomial is the zero polynomial. This problem classicaly has polynomial-time *randomized* algorithms. On the other hand, despite massive research efforts, efficient deterministic algorithms are unknown, and for a reason: By a result of Kabanets-Impagliazzo, such an algorithm would imply strong circuit lower bounds. In this talk, I will present the currently fastest algorithm for testing *determinant* polynomials for zero, which is almost as hard as the general case. We will also give a variety of algorithmic applications. The method is based on the space of partial derivatives of the determinant polynomial.
February 25, 2020 (úterý [Tuesday], 14:00, MFF UK Malá Strana, S8)
Martin Koutecký: Scheduling Kernels via Configuration LP
Abstract: Makespan minimization (on parallel identical or
unrelated machines) is arguably the most natural and studied
scheduling problem. A common approach in practical algorithm
design is to reduce the size of a given instance by a fast
preprocessing step while being able to recover key information
even after this reduction. This notion is formally studied as
kernelization (or simply, kernel) – a polynomial time procedure
which yields an equivalent instance whose size is bounded in terms
of some given parameter. It follows from known results that
makespan minimization parameterized by the longest job processing
time pmax has a kernelization yielding a reduced instance whose
size is exponential in pmax. Can this be reduced to polynomial in
pmax?
We answer this affirmatively not only for makespan minimization,
but also for the (more complicated) objective of minimizing the
weighted sum of completion times, also in the setting of unrelated
machines when the number of machine kinds is a parameter.
Our algorithm first solves the Configuration LP and based on its
solution constructs a solution of an intermediate problem, called
huge N -fold integer programming. This solution is further reduced
in size by a series of steps, until its encoding length is
polynomial in the parameters. Then, we show that huge N-fold IP is
in NP, which implies that there is a polynomial reduction back to
our scheduling problem, yielding a kernel.