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 2016 [Previous program, Spring 2016]

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:

[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 Partition shows that the problem cannot be approximated with a better absolute factor than 3/2. However, this reduction requires the numeric values to be exponentially large. In this paper, we present a (1.4 + ε)-approximation algorithm with pseudo-polynomial running time. This implies that for polynomially bounded input data the problem can be approximated with a strictly better ratio than for exponential input which is a very rare phenomenon in combinatorial optimization.

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 Partition also breaks down if we allow to drop a constant number of input items (while the compared optimal solution cannot do this). We show that then we can approximate the problem much better and present a polynomial time algorithm computing a packing of height at most (1 + ε)OPT that needs to drop at most 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:

The theorem we will use to prove all of these is a (relatively easy) consequence of the previously covered result on the MSO polytope (the polytope of satisfying assignments of a monadic second order logic formula), see Petr Kolman, Martin Koutecký, Hans Raj Tiwary: Extension Complexity, MSO Logic, and Treewidth http://arxiv.org/abs/1507.04907

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).