Dec 18, 2018, Jan 8, 2019 (úterý [Tuesday], 12:20, MFF UK
Malá Strana S10)
Michael Lampis: Parameterized Approximation Schemes using
Graph Widths. https://arxiv.org/abs/1311.2466.
(presented by Michal Berg)
Abstract: Combining the techniques of approximation
algorithms and parameterized complexity has long been considered a
promising research area, but relatively few results are currently
known. In this paper we study the parameterized approximability of
a number of problems which are known to be hard to solve exactly
when parameterized by treewidth or clique-width. Our main
contribution is to present a natural randomized rounding technique
that extends well-known ideas and can be used for both of these
widths. Applying this very generic technique we obtain
approximation schemes for a number of problems, evading both
polynomial-time inapproximability and parameterized intractability
bounds.
Nov 27, 2018 (úterý [Tuesday], 12:20, MFF UK Malá Strana
S10)
Zachary Friggstad (U. Alberta): Approximation Algorithms for
Orienteering Problems
Abstract: In the Orienteering problem, the goal is to find
a length-bounded path starting from some depot that visits the
maximum number of clients possible. For example, how many packages
can be delivered by a delivery truck in a single day?
We survey some approximations for this problem. Rather than
focusing on a single result, this talk will present a range of
approximations including the original approaches based on dynamic
programming and more recent approaches based on linear
programming. Our discussion will mostly cover constant-factor
approximations for Orienteering in symmetric metrics but sometime
will be spent on poly-logarithmic approximations for Orienteering
in asymmetric metrics.
Nov 20, 2018 (úterý [Tuesday], 12:20, MFF UK Malá Strana S10)
Uriel Feige, Mohammad Mahdian: Finding
small balanced separators. STOC 2006.
(presented by Matěj Lieskovský)
Abstract: Let G be an n-vertex graph that has a vertex separator of size k that partitions the graph into connected components of size smaller than α n, for some fixed 2/3 ≤ α < 1. Such a separator is called an α-separator. Finding an α-separator of size at most k is NP-hard. Moreover, under reasonable complexity theoretic assumptions, it is shown that this problem is not polynomially solvable even when k=O(log n). In this paper, we give a randomized algorithm that finds an α-separator of size k in the given graph, unless the graph contains an (α+ε)-separator of size strictly less than k, in which case our algorithm finds one such separator. For fixed ε, the running time of our algorithm is nO(1)2O(k), which is polynomial for k = O(log n). For bounded degree graphs (as well as for the case of finding balanced edge separators), we present a deterministic algorithm with similar running time.Our algorithm involves (among other things) a new concept that we call (ε,k)-samples. This is related to the notion of detection sets for network failures, introduced by Kleinberg [FOCS 2000]. Our proofs adapt and simplify techniques that were introduced by Kleinberg. As a by-product, our proof improves the known bounds on the size of detection sets. We also show applications of (ε,k)-samples to problems in approximation algorithms and rigorous analysis of heuristics.
Nov 6, Nov 13, 2018 (úterý [Tuesday], 12:20, MFF UK Malá Strana S10)Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket
Saurabh: Lossy
Kernelization. STOC 2017. Also https://arxiv.org/abs/1604.04111.
(presented by Pavel Dvořák)
Abstract: In this paper we propose a new framework for
analyzing the performance of preprocessing algorithms. Our
framework builds on the notion of kernelization from parameterized
complexity. However, as opposed to the original notion of
kernelization, our definitions com- bine well with approximation
algorithms and heuristics. The key new definition is that of a
polynomial size α-approximate kernel. Loosely speaking, a
polynomial size α-approximate kernel is a polynomial time
pre-processing algorithm that takes as input an instance (I,
k) to a parameterized problem, and outputs another instance
(I′,k′) to the same problem, such that |I′| +
k′ ≤ kO(1). Additionally, for
every c ≥ 1, a c-approximate solution s′
to the pre-processed instance (I′, k′) can be
turned in polynomial time into a (c · α)-approximate
solution s to the original instance (I,k).
Amongst our main technical contributions are α-approximate kernels of polynomial size for three problems, namely Connected Vertex Cover, Disjoint Cycle Packing and Disjoint Factors. These problems are known not to admit any polynomial size kernels unless NP ⊆ coNP/Poly. Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size, and the hardness of approximation lower bounds for all three problems. On the negative side we prove that Longest Path parameterized by the length of the path and Set Cover parameterized by the universe size do not admit even an α-approximate kernel of polynomial size, for any α≥1, unless NP ⊆ coNP/Poly. In order to prove this lower bound we need to combine in a non-trivial way the techniques used for showing kernelization lower bounds with the methods for showing hardness of approximation.
Oct 23, Oct 30, 2018 (úterý [Tuesday], 12:20, MFF UK Malá Strana S10)
Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi: On the
Parameterized Complexity of Approximating Dominating Set.
STOC 2018. Also at https://arxiv.org/abs/1711.11029.
(presented by Ashutosh Rai)
Abstract: We study the parameterized complexity of
approximating the $k$-Dominating Set (DomSet) problem where an
integer $k$ and a graph $G$ on $n$ vertices are given as input,
and the goal is to find a dominating set of size at most $F(k)
\cdot k$ whenever the graph $G$ has a dominating set of size $k$.
When such an algorithm runs in time $T(k) \cdot poly(n)$ (i.e.,
FPT-time) for some computable function $T$, it is said to be an
$F(k)$-FPT-approximation algorithm for $k$-DomSet. We prove the
following for every computable functions $T, F$ and every constant
$\varepsilon > 0$:
Our results are obtained by establishing a connection between communication complexity and hardness of approximation, generalizing the ideas from a recent breakthrough work of Abboud et al. [FOCS 2017]. Specifically, we show that to prove hardness of approximation of a certain parameterized variant of the label cover problem, it suffices to devise a specific protocol for a communication problem that depends on which hypothesis we rely on. Each of these communication problems turns out to be either a well studied problem or a variant of one; this allows us to easily apply known techniques to solve them.
Oct 16, 2018 (úterý [Tuesday], 12:20, MFF UK Malá Strana S10)
Jiří Sgall: Online algorithms for packet scheduling
Abstract: We survey recent and older results in this area.
Oct 9, 2018 (úterý [Tuesday], 12:20, MFF UK Malá Strana S10)
Andreas Emil Feldmann: Parametrized Approximation
Algorithms - An Introduction.
Abstract: Two of the most prevalent algorithm-design paradigms for NP-hard problems are approximations and fixed-parameter tractability. The former sacrifices on the accuracy of the output, but demands polynomial runtime of the algorithms. The latter demands an exact solution, but any super-polynomial runtime is confined to a parameter describing some property of the input. So far, the two areas of approximation and fixed-parameter tractability have mostly been developed separately. In this endeavour, the limitations of these approaches have also become apparent, as many problems can provably be shown not to admit any reasonable algorithms in either of these regimes. To lift us out of this dilemma, we explore the unified regime of parameterized approximation algorithms. These algorithms aim to be much faster than any exact algorithm while only sacrificing very little in accuracy.