5. 1., 19. 1. 2018 (pátek [Friday], 10:40, MFF UK Malá
Strana S6)
Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu: Linear
programming relaxations for Maxcut. SODA 2007.
(presented by Jakub Sosnovec)
Abstract: It is well-known that the integrality gap of the usual linear programming relaxation for Maxcut is 2 - ε. For general graphs, we prove that for any ε and any fixed bound k, adding linear constraints of support bounded by k does not reduce the gap below 2 - ε. We generalize this to prove that for any ε and any fixed bound k, strengthening the usual linear programming relaxation by doing κ rounds of Sherali-Adams lift-and-project does not reduce the gap below 2 - ε. On the other hand, we prove that for dense graphs, this gap drops to 1 + ε after adding all linear constraints of support bounded by some constant depending on ε.
12. 1. 2018 (pátek [Friday], 10:40, MFF UK Malá Strana S6)
Martin Koutecký: Multitype Monoid Decomposition &
Applications in Parameterized Scheduling.
(joint work with Dušan Knop, Asaf Levin, Matthias Mnich and
Shmuel Onn)
Abstract: In the Monoid Decomposition problem we are given
a set of d-dimensional integer vectors X and a d-dimensional
vector n, and we are asked to decompose n into elements of X. This
problem naturally models the configuration ILP approach to many
scheduling and packing problems, where we have a set of
configurations X and we ask whether a vector of job or item
multiplicities n can be decomposed into these configurations,
implying that a scheduling or a packing exists.
The famous Cutting Stock problem can be viewed as a Multitype
Monoid Decomposition (MMD) problem, because there are distinct
sets X_1, ..., X_\tau of configurations for \tau distinct types of
rolls; we can similarly express various scheduling problems on
unrelated machines. Goemans and Rothvoss gave an algorithm which
can be interpreted as solving MMD in time which is fixed-parameter
tractable for parameters number of types \tau and dimension of X_i
d, if the input (vector n and sets X_i represented by linear
inequalities) is given in unary.
We show an orthogonal result, namely that MMD is fixed-parameter
tractable for parameter largest coefficient in inequality
description of X_1, ..., X_\tau, but with \tau polynomial and n
given in binary. This leads to improved runtimes of some existing
scheduling algorithms, and in new parameterized scheduling
algorithms for R | pmtn, r_ij, d_ij | C_max, R | r_ij, d_ij |
C_max and R | r_ij, d_ij | \sum c_j U_j , where U_j is an
indicator that job j is late. Our result follows from a new FPT
algorithm for "huge" (high multiplicity) n-fold integer
programming, which is obtained by proving a new proximity theorem
and then applying a
recent (faster) algorithm for regular n-fold IP.
15. 12., 22. 12. 2017 (pátek [Friday], 10:40, MFF UK Malá
Strana S6)
Ola Svensson, Jakub Tarnawski, László A. Végh: A Constant-Factor
Approximation Algorithm for the Asymmetric Traveling Salesman
Problem. https://arxiv.org/abs/1708.04215.
(presented by Pavel Veselý)
Abstract: We give a constant-factor approximation
algorithm for the asymmetric traveling salesman problem. Our
approximation guarantee is analyzed with respect to the standard
LP relaxation, and thus our result confirms the conjectured
constant integrality gap of that relaxation.
Our techniques build upon the constant-factor approximation
algorithm for the special case of node-weighted metrics.
Specifically, we give a generic reduction to structured instances
that resemble but are more general than those arising from
node-weighted metrics. For those instances, we then solve
Local-Connectivity ATSP, a problem known to be equivalent (in
terms of constant-factor approximation) to the asymmetric
traveling salesman problem.
8. 12. 2017 (pátek [Friday], 10:40, MFF UK Malá Strana S6)
Andreas Emil Feldmann: Parameterized approximation algorithms
for directed Steiner network problems in bidirected graphs.
Abstract: Given an edge-weighted directed graph
G=(V,E) and a set of d terminal pairs (s_1,t_1),...,(s_d,t_d), the
objective of the Directed Steiner Network (DSN) problem is to
compute the cheapest subgraph N of G such that there is an s_i
-> t_i path in N for every i. This problem is notoriously hard,
even in the realm of parameterized approximation: for the
well-studied parameter k=|{s_i,t_i}|, i.e. the number of
terminals, it was recently shown by [Dinur & Manurangsi, 2017]
that under Gap-ETH no d^{1/4-o(1)}-approximation is possible for
DSN in f(k)*poly(n) time, for any function f(k). The main question
we explore is: what approximation factors and runtimes are
possible for special cases of DSN when parametrizing by the number
of terminals k?
For problems related to DSN it has been fruitful before to analyze
the structure of the optimum in order to obtain approximation and
FPT algorithms. Therefore, we consider the DSN_K problem, where we
need to compute the optimum network contained in some class K of
graphs. If K for instance is the class of planar graphs, then this
generalizes several well-studied special cases, such as DSN on
planar input graphs, but also the Directed Steiner Tree problem on
general input graphs. Our main result proves that if additionally
the input is bidirected, then a parameterized approximation scheme
exists if we aim to compute the planar optimum. We also provide
several hardness results that show that our obtained runtime is
the best possible for this special case, while at the same time no
parameterized approximation scheme exists for any generalization
of this special case. We also consider the Strongly Connected
Steiner Subgraph (SCSS) problem as another special case, which
cannot be captured by DSN_K for any non-trivial class K. We prove
that a known parameterized 2-approximation is best possible for
SCSS, and that on bidirected input graphs the problem is FPT for
parameter k.
10. 11., 24. 11. 2017 (pátek [Friday], 10:40, MFF UK Malá Strana S6)
Ola Svensson: Approximating
ATSP by Relaxing Connectivity. FOCS 2015. Also https://arxiv.org/abs/1502.02051.
(presented by Martin Böhm)
Abstract: The standard LP relaxation of the asymmetric
traveling salesman problem has been conjectured to have a constant
integrality gap in the metric case. We prove this conjecture when
restricted to shortest path metrics of node-weighted digraphs. Our
arguments are constructive and give a constant factor
approximation algorithm for these metrics. We remark that the
considered case is more general than the directed analog of the
special case of the symmetric traveling salesman problem for
which there were recent improvements on Christofides' algorithm.
27. 10., 3. 11. 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)
Abstract: We study the classical scheduling problem of assigning jobs to machines in order to minimize the makespan. It is well-studied and admits an EPTAS on identical machines and a (2-1/m)-approximation algorithm on unrelated machines. In this paper we study a variation in which the input jobs are partitioned into bags and no two jobs from the same bag are allowed to be assigned on the same machine. Such a constraint can easily arise, e.g., due to system stability and redundancy considerations. Unfortunately, as we demonstrate in this paper, the techniques of the above results break down in the presence of these additional constraints. Our first result is a PTAS for the case of identical machines. It enhances the methods from the known (E)PTASs by a finer classification of the input jobs and careful argumentations why a good schedule exists after enumerating over the large jobs. For unrelated machines, we prove that there can be no (log n)^{1/4-epsilon}-approximation algorithm for the problem for any epsilon > 0, assuming that NP nsubseteq ZPTIME(2^{(log n)^{O(1)}}). This holds even in the restricted assignment setting. However, we identify a special case of the latter in which we can do better: if the same set of machines we give an 8-approximation algorithm. It is based on rounding the LP-relaxation of the problem in phases and adjusting the residual fractional solution after each phase to order to respect the bag constraints.
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})$.
We will survey known results about the problem and present several new ones. In particular, we will show that for planar and for bounded genus graphs, the problem is fixed parameter tractable (FPT) with respect to $L$, and for graphs of treewidth bounded by $\tau$, we describe $\tau$-approximation algorithm for a vertex version of the problem. We will also discuss related open problems.