Seminar on Approximation and Online Algorithms

**22. 5. 2017** (pondělí [Monday], 12:20, MFF UK Malá Strana
S4)

**Martin Böhm: Halfspace chasing**

(Based on joint ongoing work with Nikhil Bansal, Marek Eliáš,
Grigorios Koumoutsos and Seeun William Umboh.)

Abstract: In the halfspace chasing problem, we start at the origin
of R^d, and then a sequence of halfspaces of R^d arrive online.
After each halfspace arrives, we have to change our position to
one inside the halfspace. After the input ends, we compare our
total length of the motion with the total length of the motion of
an adversary which knew the entire instance in advance. The
problem has been introduced by Friedman and Linial in 1993, in a
fairly complicated introductory paper. A lower bound of sqrt(d) is
known and a constant-competitive algorithm for R^2 is known, but
the rest is open. We will show a much simplified analysis for the
2-dimensional case based on the ideas of Friedman and Linial. We
will also describe a very "fresh out of the oven"
constant-competitive algorithm for any fixed dimension provided
that there exists a point in the intersection of all the
halfspaces.

**15. 5. 2017** (pondělí [Monday], 12:20, MFF UK Malá Strana
S4)

**Lukáš Folwarczný: A Variation of the Stackelberg MST Game**

**Abstract:**** **The Stackelberg Minimum Spanning Tree
game is a one-round two-player network pricing game. In the talk,
I will prove that an optimal strategy in a natural variant of the
standard game setting is NP-hard to compute.

**24. 4. 2017** (pondělí [Monday], 12:20, MFF UK Malá Strana
S4)

** Morteza Monemizadeh: Testable Bounded Degree Graph
Properties Are Random Order Streamable.**ICALP 2017.

Abstract:

**10. 4. 2017** (pondělí [Monday], 12:20, MFF UK Malá Strana
S4)

** Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, Hang Zhou:
To
Augment or Not to Augment: Solving Unsplittable Flow on a
Path by Creating Slack.** SODA 2017: 2411-2422.

(referuje Štěpán Šimsa)

Abstract:

**3. 4. 2017** (pondělí [Monday], 12:20, MFF UK Malá Strana
S4)

Abstract:

**20. 3., 27.3. 2017** (pondělí [Monday], 12:20, MFF UK Malá
Strana S4)

**Rebecca Hoberg and Thomas Rothvoss: A
Logarithmic Additive Integrality Gap for Bin Packing. **SODA
2017: 2616-2625.

(referuje Pavel Veselý)

**Abstract:**** **For *bin packing*, the input
consists of *n* items with sizes s_{1},…, *s _{n}
*in [0,1] which have to be assigned to a minimum number of bins
of size 1. Recently, the second author gave an LP-based polynomial
time algorithm that employed techniques from

**6. 3., 13. 3. 2017** (pondělí [Monday], 12:20, MFF UK Malá
Strana S4)

**Martin Koutecký: Fast Parameterized Algorithms via n-fold
Integer Programming**

(joint work with Dušan Knop and Matthias Mnich)

However, this result had a drawback: Take for example the Swap Bribery problem, where there are n voters and we are asked to bribe them in a certain way. While the previous (double-exponential) algorithm had the runtime logarithmic in n, the new (single-exp) algorithm has runtime cubic in n. In this talk we will show how, by analyzing and enhancing the algorithm for n-fold IP, we can give single-exponential algorithms in time logarithmic in n.

**27. 2. 2017** (pondělí [Monday], 12:20, MFF UK Malá Strana
S4)

**Dušan Knop: Target Set Selection in Dense Graph Classes**

(joint work with Pavel Dvořák and Tomáš Toufar)

We give two parameterized algorithms for a special case where each vertex has threshold set to half of its neighbors (the so called Majority Target Set Selection problem) for parameterizations by neighborhood diversity and twin cover number of the input graph.

From the opposite side we give hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width – a natural generalization of both previous structural parameters. We show that the Target Set Selection problem parameterized by the neighborhood diversity when there is no restriction on the thresholds is W[1]-hard. Finally, we derive from the modular-width result for Majority Target Set Selection that the problem is paraNP-hard with respect to shrub-depth parameter. This is not immediate as there is no relation between these two graph parameters in general.