22. 5. 2017 (pondělí [Monday], 12:20, MFF UK Malá Strana
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
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.
(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:
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
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
(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
(joint work with Dušan Knop and Matthias Mnich)
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)