Seminar on Approximation and Online Algorithms

**24. 5. 2016** (úterý [Tuesday], 14:00, MFF UK Malá Strana
S7)

**Pavel Vesely: Plan based algorithm for packet scheduling
**(joint work with Marek Chrobak)

**Abstract: **In online packet scheduling, unit sized packets
arrive in an online fashion, each with an associated deadline and
weight. The packets can be kept in memory indefinitely, but can be
sent only before their deadline. Only one packet can be
transmitted in each timeslot. The goal is to maximize weight of
the transmitted packets. The main open question is whether there
is an algorithm with competitive ratio equal to phi, the golden
ratio (approx. 1.618). We show a lower bound bigger than phi for
algorithms satisfying certain conditions.

Then we explain an algorithm based on the plan which is the
optimal schedule of pending packets assuming that no other packets
arrive. It is an open question whether this algorithm is
phi-competitive or not.

** 17. 5. 2016** (úterý [Tuesday], 14:00, MFF UK Malá
Strana S7)

**Jiri Sgall: Simplified Online Packet Scheduling under
Adversarial Jamming
(joint work with M. Bohm, L. Jez, P. Vesely)
Abstract: **Following [1], we study the following problem.
Packets of arbitrary sizes arrive over time. An online algorithm
is to maximize the total size of packets it transmits. There are
(instantaneous) jamming errors at times chosen by the adversary
and not known to the algorithm. A transmission taking place at the
time of jamming is corrupt, and the algorithm learns this fact
immediately. The goal is to develop an algorithm with lowest
possible asymptotic competitive ratio, where the additive constant
may depend on sizes of packets.

For the case of divisible sizes of packets, we develop algorithm which is 2-competitive with speed 1 and 1-competitive with speed 2. For general sizes, our algorithm is 3-competitive with speed 1 and 1-competitive with speed 6.

Compared to [1], our algorithm has the following desirable features:

- it is always busy, in the sense that it always transmits some packet if there are any pending,
- it does not need to know all possible packet sizes nor their number,
- it works for any speedup s; s does not need to be known in
advance.

[1] Tomasz Jurdzinski, Dariusz R. Kowalski, and Krzysztof Lorys:
Online packet scheduling under adversarial jamming. ArXiv
1310.4935, 2013.

**10. 5. 2016 **(úterý [Tuesday], 14:00, MFF UK Malá Strana
S7)

**F. Bruce Shepherd, Adrian Vetta: The Inapproximability of
Maximum Single-Sink Unsplittable, Priority and Confluent Flow
Problems. **http://arxiv.org/abs/1504.00627.

(referuje Petr Kolman)

**Abstract:** We consider single-sink network flow problems.
An instance consists of a capacitated graph (directed or
undirected), a sink node t and a set of demands that we want to
send to the sink. Here demand i is located at a node s_i and
requests an amount d_i of flow capacity in order to route
successfully. Two standard objectives are to maximise (i) the
number of demands (cardinality) and (ii) the total demand
(throughput) that can be routed subject to the capacity
constraints. Furthermore, we examine these maximisation problems
for three specialised types of network flow: unsplittable,
confluent and priority flows.

In the unsplittable flow problem (UFP), we have edge capacities,
and the demand for s_i must be routed on a single path. In
the confluent flow problem, we have node capacities, and the
final flow must induce a tree. Both of these problems have been
studied extensively, primarily in the single-sink setting.
However, most of this work imposed the {\em no-bottleneck
assumption} (that the maximum demand d_max is at most the minimum
capacity u_min). Given the no-bottleneck assumption (NBA), there
is a factor 4.43-approximation algorithm due to Dinitz et al. for
the unsplittable flow problem. Under the stronger assumption of
uniform capacities, there is a factor 3-approximation algorithm
due to Chen et al. for the confluent flow problem. However, unlike
the UFP, we show that a constant factor approximation algorithm
cannot be obtained for the single-sink confluent flows even with
the NBA.

Without NBA, we show that maximum cardinality single-sink UFP is
hard to approximate to within a factor n^(0.5-\eps) even when all
demands lie in a small interval [1,1+delta] where delta>0 (but
has polynomial input size). This is very sharp since when delta=0,
this becomes a maximum flow problem.

**3. 5. **(úterý [Tuesday], 14:00, MFF UK Malá Strana S7)

**Dušan Knop, Martin Koutecký: Applications of the n-fold IP
technique and open problems**

**Abstract:** We will briefly recall the tool of n-fold
integer programming and show two applications: in scheduling (the
P||C_max problem) and to the Closest String problem. Both
applications yield FPT results which have been

known, but using n-fold IP gives exponentially better runtimes.
Thus we are interested in proving lower bounds - how close are we
to the optimum? Also, we believe some estimates made for the
general n-fold IP problem might be too pessimistic in our specific
instances and that the actual runtime is even better, but we
cannot prove this currently. We will present these open problems
in an accessible way.

**19. 4., 26. 4. 2016 **(úterý [Tuesday], 14:00, MFF UK Malá
Strana S7)

** Giorgi Nadiradze and Andreas Wiese. On
approximating strip packing with a better ratio than 3/2.
SODA 2016.
**(referuje Pavel Veselý)

**Abstract:** In the strip packing problem we are given a set
of rectangular items that we want to place in a strip of given
width such that we minimize the height of the obtained packing. It
is a very classical two-dimensional packing problem that has
received a lot of attention and it has applications in many
settings such as stock-cutting and scheduling. A straight-forward
reduction from P

Our algorithm is based on a structural lemma proving that there
is a packing of height (1.4 + ε)*OPT* that allows a partition
of the packing area into few rectangular boxes. These boxes have
the property that they decouple the packing decisions for the
items that are thin and high, wide and narrow, or large in both
dimensions. The interaction of these item types is typically a
major problem when designing algorithms and our partition
completely solves this. Particularly difficult are items that are
thin and high since a single one of them can increase the optimal
packing height significantly if placed wrongly and there can be up
to Ω(*n*) of them. For those items the box partition is even
fine grained enough so that all items in a box have essentially
the same height. This reduces the usually difficult packing
decisions for these items to a problem that can be solved easily
via a pseudo-polynomial time dynamic program.

The mentioned reduction from P*O*_{ε}(1) items.

**5. 4. 2016 **(úterý [Tuesday], 14:00, MFF UK Malá Strana
S7)

**Martin Koutecký: ****Metatheorems simplified**

**Abstract:** Algorithmic metatheorems like Courcelle's
theorem are powerful tools in parameterized complexity for proving
several tractability results at once which makes them highly
relevant. On the other hand, it seems that most of their proofs
are quite involved. Moreover, when one wants to show an extension
of metatheorems like Courcelle's, it seems hard to "interface"
with existing results in order not to "reinvent the wheel", that
is, reprove

already known results.

We will state (but not prove) a theorem connecting Courcelle's
theorem to linear programming and other geometrical concepts and
derive several old and new results using this theorem, namely:

- an extension of Courcelle's theorem to
- optimizing so-called fair objectives,
- having so-called cardinality constraints and

- local cardinality constraints

- an algorithm for MSO-partitioning

- an algorithm for the so-called shifted problem (which
generalizes MSO-partitioning and several other previously
studied problems).

**29. 3. 2016 **(úterý [Tuesday], 14:00, MFF UK Malá Strana
S7)

**Daniel Lokshtanov: Parameterized Integer Quadratic
Programming: Variables and Coefficients.** http://arxiv.org/abs/1511.00310.

(referuje Martin Koutecký)

**Abstract:** In the Integer Quadratic Programming problem
input is an n*n integer matrix Q, an m*n integer matrix A and an
m-dimensional integer vector b. The task is to find a vector x in
Z^n, nminimizing x^TQx, subject to Ax <= b. We give a fixed
parameter tractable algorithm for Integer Quadratic Programming
parameterized by n+a, assuming that an optimal solution to the
input instance exists. Here a is the largest absolute value of an
entry of Q and A. As an application of our main result we show
that Optimal Linear Arrangement is fixed parameter tractable
parameterized by the size of the smallest vertex cover of the
input graph. This resolves an open problem from the recent
monograph by Downey and Fellows.

**15. 3., 22. 3. 2016 **(úterý [Tuesday], 14:00, MFF UK Malá
Strana S7)

**Subhash Khot, Dana Moshkovitz: Candidate Hard Unique Game.
STOC 2016.**

(presented by Martin Böhm)

**Abstract: **We propose a candidate reduction for ruling out
polynomial-time algorithms for unique games, either under
plausible complexity assumptions, or unconditionally for Lasserre
semidefinite programs with a constant number of rounds. We analyze
the completeness and Lasserre solution of our construction, and
provide a soundness analysis in a certain setting of interest.
Addressing general settings is tightly connected to a question on
Gaussian isoperimetry.

The paper will be presented in two sessions. In the first session,
we will get (re)acquainted with the Unique Games conjecture and
its variants, Lasserre programs for CSPs, inner/outer verifiers,
the use of codes in PCP theorems and the two most-often used
codes: the Hadamard code and the long code. We will also define
the newly proposed code (the real code) and state the main results
of this work. In the second session (next week), we will see a bit
more of the paper itself. The presentation should be accessible to
anyone with basic knowledge of the PCP theorem and semidefinite
programming.

**1. 3., 8. 3. 2016 **(úterý [Tuesday], 14:00, MFF UK Malá
Strana S7)

**Julia Chuzhoy: Improved Bounds for the Excluded Grid Theorem.
**http://arxiv.org/abs/1602.02629.

(referuje Dušan Knop)

**Abstract: **We study the Excluded Grid Theorem of
Robertson and Seymour. This is a fundamental result in graph
theory, that states that there is some function f:Z+→Z+, such that
for all integers g>0, every graph of treewidth at least f(g)
contains the (g×g)-grid as a minor. Until recently, the best known
upper bounds on f were super-exponential in g. A recent work of
Chekuri and Chuzhoy provided the first polynomial bound, by
showing that treewidth f(g)=O(g^{98}polylog(g)) is sufficient to
ensure the existence of the (g×g)-grid minor in any graph. In this
paper we improve this bound to f(g)=O(g19polylogg). We introduce a
number of new techniques, including a conceptually simple and
almost entirely self-contained proof of the theorem that achieves
a polynomial bound on f(g).