Pavel Veselý

Given an edge-weighted undirected graph the Steiner Tree problem asks to compute a minimum weight tree that spans all the terminals. This problem is APX-hard and W[1]-hard when parameterized by the number of Steiner vertices (non-terminals) in an optimal solution (it is FPT w.r.t. parametrization by the number of terminals). We overcame both these lower bounds by combining the paradigms of approximation and parametrization. More precisely, we desinged an efficient parameterized approximation scheme, i.e., a (1+epsilon)-approximation in time f(epsilon, p)*poly(n) where p is the parameter. Our algorithm works also for a more general problem, namely Steiner Forest with a low number of components in an optimal solution, and can be seen as a preprocessing algorithm that iteratively decreses the number of terminals by contracting stars with a good ratio. As a consequence we also obtain a lossy kernel (i.e., a kernel preserving solutions only approximately). We also have some results for the directed version of the problem.

We study online scheduling of packets over a channel prone to adversarial jamming errors which interrupt the current transmission (the transmitted packet needs to be resend completely). The distinguishing feature is that packets have small (constant) sizes and the number of sizes is also small. We designed a universal algorithm which works well for any sizes and any speedup (which is a resource augmentation), together with a universal framework how to analyze it locally, which however does not give tight results in all settings. Our main and probably the most interesting result is that our algorithm needs speed 4 to be 1-competitive which is shown by a more sophisticated non-local analysis. We complemented it by a nice lower bound of 2.618 (the golden ratio + 1) on the speedup of any deterministic 1-competitive algorithm.

We proved PSPACE-hardness of online coloring in which vertices of a known graph G arrives online and Painter colors them immediately without knowing to which induced subgraph of G the colored vertices correspond. Previously, PSPACE-hardness was known only in the variant in which some part of the graph is precolored (which makes the hardness proof substantially easier).

In Online Packet Scheduling problem, packets arrive online into a buffer, each with a deadline, a weight, and of length 1. The goal is to schedule a packet in each time slot to maximize the total weight of scheduled packets. There is a lower bound of phi (the golden ratio, approx. 1.618) on the competitive ratio of deterministic algorithms and it is an important open problem to find a matching algorithm, or to improve the lower bound. In this paper we show a phi-competitive algorithm for a restricted class of instances, called 4-bounded instances, in which a packet arriving at time t has deadline at most t+4. Moreover, we introduced a model with a resource augmentation, namely with lookahead which allows the algorithm to look a little bit into the future. We obtained a nearly tight results for the 2-bounded case with 1-lookahead.

In Online Multi-Level Aggregation (which is a generalization of TCP Acknowledgment and Joint Replenishment Problem) requests are arriving to nodes of an edge-weighted rooted tree and an online algorithm has to serve them by sending a rooted subtree, paying the cost of this subtree. The objective is to minimize the total cost of all subtrees sent plus the total waiting cost of requests. Among other results we designed the first O(1)-competitive algorithm for trees of bounded height, although with exponential dependence on the height.

We study a variant of online bin packing with guarantees. There are m bins and we know that the optimum solution packs all items into these bins when they have capacity 1. The goal of the algorithm is to pack the same items into m bins with capacity R > 1, for as small R as possible. (This is equivalent to online makespan minimization scheduling with known optimum.) Our main result is an algorithm which has R = 1.5 and we also have a better algorithm for 3 bins. The main open problem is to improve upon the simple lower bound of 4/3, which holds for m >= 2 bins.

In Colored Bin Packing each item has a color in addition to size and the goal is to pack those items online into bins with capacity 1 such that no two items packed consecutively into a bin have the same color. The problem is interesting even when all sizes are 0 and we found an optimal algorithm for this special case together with a matching lower bound. The analysis of the optimal algorithm is in my opinion the most interesting part of the paper. We designed a (simple) algorithm and a lower bound for the general case, both generalizing previous results for two colors. Moreover, for two colors we give a tight analysis of a class of simple algorithms, called Any Fit algorithms.

We analyzed a recent board game Tzaar (a part of the Gipf project) and implemented an artificial intelligence to play the game. We let it play on Boiteajeux, an online board gaming portal, and it was able to match the level of best players on the portal (in 2013). We also propose an enhancement of Proof-number Search.

We study online scheduling of packets over a channel prone to adversarial jamming errors which interrupt the current transmission (the transmitted packet needs to be resend completely). The distinguishing feature is that packets have small (constant) sizes and the number of sizes is also small. We designed a universal algorithm which works well for any sizes and any speedup (which is a resource augmentation), together with a universal framework how to analyze it locally, which however does not give tight results in all settings. Our main and probably the most interesting result is that our algorithm needs speed 4 to be 1-competitive which is shown by a more sophisticated non-local analysis. We complemented it by a nice lower bound of 2.618 (the golden ratio + 1) on the speedup of any deterministic 1-competitive algorithm.

In Online Packet Scheduling problem, packets arrive online into a buffer, each with a deadline, a weight, and of length 1. The goal is to schedule a packet in each time slot to maximize the total weight of scheduled packets. There is a lower bound of phi (the golden ratio, approx. 1.618) on the competitive ratio of deterministic algorithms and it is an important open problem to find a matching algorithm, or to improve the lower bound. In this paper we show a phi-competitive algorithm for a restricted class of instances, called 4-bounded instances, in which a packet arriving at time t has deadline at most t+4. Moreover, we introduced a model with a resource augmentation, namely with lookahead which allows the algorithm to look a little bit into the future. We obtained a nearly tight results for the 2-bounded case with 1-lookahead.

We proved PSPACE-hardness of online coloring in which vertices of a known graph G arrives online and Painter colors them immediately without knowing to which induced subgraph of G the colored vertices correspond. Previously, PSPACE-hardness was known only in the variant in which some part of the graph is precolored (which makes the hardness proof substantially easier).

We consider the reordering buffer problem on a line consisting of n equidistant points. We show that, for any constant delta, an (offline) algorithm that has a buffer (1-delta) k performs worse by a factor of Omega(log n) than an offline algorithm with buffer k. In particular, this demonstrates that the O(log n)-competitive online algorithm MovingPartition by Gamzu and Segev (ACM Trans. on Algorithms, 6(1), 2009) is essentially optimal against any offline algorithm with a slightly larger buffer.

In Online Multi-Level Aggregation (which is a generalization of TCP Acknowledgment and Joint Replenishment Problem) requests are arriving to nodes of an edge-weighted rooted tree and an online algorithm has to serve them by sending a rooted subtree, paying the cost of this subtree. The objective is to minimize the total cost of all subtrees sent plus the total waiting cost of requests. Among other results we designed the first O(1)-competitive algorithm for trees of bounded height, although with exponential dependence on the height.

We study a variant of online bin packing with guarantees. There are m bins and we know that the optimum solution packs all items into these bins when they have capacity 1. The goal of the algorithm is to pack the same items into m bins with capacity R > 1, for as small R as possible. (This is equivalent to online makespan minimization scheduling with known optimum.) We designed an algorithm with R = 1.5. The main open problem is to improve upon the simple lower bound of 4/3, which holds for m >= 2 bins.

We study a variant of online bin packing with guarantees. There are m bins and we know that the optimum solution packs all items into these bins when they have capacity 1. The goal of the algorithm is to pack the same items into m bins with capacity R > 1, for as small R as possible. (This is equivalent to online makespan minimization scheduling with known optimum.) We present an algorithm for 3 bins and also improved lower bounds for 3, 4, and 5 bins, using computer program shows a strategy for the adversary in the underlying two-player game. The main open problem is to improve upon the simple lower bound of 4/3, which holds for m >= 2 bins.

In Colored Bin Packing each item has a color in addition to size and the goal is to pack those items online into bins with capacity 1 such that no two items packed consecutively into a bin have the same color. The problem is interesting even when all sizes are 0 and we found an optimal algorithm for this special case together with a matching lower bound. The analysis of the optimal algorithm is in my opinion the most interesting part of the paper. We designed a (simple) algorithm and a lower bound for the general case, both generalizing previous results for two colors. Moreover, for two colors we give a tight analysis of a class of simple algorithms, called Any Fit algorithms.