Seminář z aproximačních a online algoritmů
Seminar on Approximation and Online Algorithms

Petr Kolman, Jiří Sgall

Předchozí program semináře, letní semestr 2017 [Previous program, Spring 2017]

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.
(joint work with S. Muthukrishnan, Pan Peng, and Christian Sohler)
 
Abstract: We study graph streaming problems. We  transform known property testing algorithms into streaming ones. In particular, our main result is that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in single-pass random order model. Our results are obtained by estimating the distribution of local neighborhoods of the vertices on a random order graph stream using constant space. We also apply this approach to constant time approximation algorithms in the adjacency list model and get single-pass random order streaming algorithms for all of them. For example, we get constant-space single-pass random order streaming algorithms for approximating the size of a maximum matching with additive error $\epsilon n$ ($n$ is the number of nodes). Our results are among the first known constant space graph streaming algorithms, while $\Omega(n)$ space is needed for many graph streaming problems and previous results typically use the semi-streaming model of $O(n\cdot \poly\log n)$ space.

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: In the Unsplittable Flow on a Path problem (UFP) we are given a path with non-negative edge capacities and a set of tasks, each one characterized by a subpath, a demand, and a profit. Our goal is to select a subset of tasks of maximum total profit so that the total demand of the selected tasks on each edge does not exceed the respective edge capacity. UFP naturally captures several applications in bandwidth allocation, job scheduling, and caching. Following a sequence of improvements, the current best (polynomial time) approximation factor for UFP is 2+eps [Anagnostopoulos et al. SODA'14]. UFP also admits a QPTAS [Bansal et al. STOC'06, Batra et al. SODA'15], and finding a PTAS is considered a challenging open problem. In this paper we make progress in the direction of the mentioned open problem. Informally, we introduce a technique to obtain real PTASs from PTASs with resource augmentation where edge capacities can be violated by a 1+eps factor. While unfortunately we do not have a resource-augmentation PTAS for the general case of UFP, for many relevant special cases we have such an algorithm or we provide one in this paper. For example, our approach leads to a PTAS for the rooted case of UFP, where all tasks share a common edge. This is one of the simplest natural restrictions of UFP where the best-known approximation was 2+eps (like for the general case).

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

Petr Kolman: Length-bounded cuts

Abstract: Given a graph $G=(V,E)$ with two distinguished vertices $s,t\in V$ and an integer parameter $L>0$, an {\em $L$-bounded cut} is a subset $F$ of edges such that the every path between $s$ and $t$ in $(V,E\setminus F)$ has length at least $L$. The task is to find an $L$-bounded cut of minimum cardinality. The problem is known to be NP-hard for $L\leq 4$. In the talk I plan to survey known results, compare the problem with other hard problems (from the perspective of approximation algorithms), review related open problems and discuss possible ways how to tackle them, as well as obstacles that restrain from doing so. Particular attention will be given to planar instances of the problem.

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 s1,…, sn 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 discrepancy theory to find a solution using at most OPT + O(logOPT * loglog OPT) bins. In this paper, we build on the techniques of Rothvoss to present an approximation algorithm that has an additive gap of only O(log OPT) bins. This gap matches certain combinatorial lower bounds, and any further improvement would have to use more algebraic structure.

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)

Abstract:  N-fold integer programming is a subcase of integer programming with linear constraints, and over time, increasingly faster algorithms have been developed for solving it. Only very recently it was discovered that n-fold IP can be used to solve in single-exponential time (in the parameter) various problems from stringology, computational social choice and other areas, for which previously only double-exponential time algorithms were known.

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)

Abstract: In this paper we study the Target Set Selection problem, a fundamental problem in computational social choice, from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex the task is to find a set of vertices to activate (called target set) which activates whole graph. A vertex outside the target set becomes active if the number of activated vertices in its neighborhood is at least its threshold.

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.