Pavel Veselý

We prove a tight lower bound for the space used by a deterministic comparison-based quantile summary, which keeps track of all quantiles in a data stream (where items are linearly ordered), up to a small error. The lower bound matches the worst-case performance of the Greenwald-Khanna algorithm, up to a constant factor, and holds even for finding an approximate median in a data stream in the comparison-based model, where an algorithm only compares items and is otherwise completely oblivious of the universe of items.

We design a 1-pass deterministic streaming algorithms for bin packing and vector scheduling. For bin packing, our streaming approximation scheme uses quantile summaries and interestingly, the connection between streaming bin packing and quantile summaries goes also in the other direction. That is, given a streaming algorithm for bin packing, we can estimate the rank of an item in the stream in the same space, which basically suffices to construct a quantile summary. For vector scheduling in dimension d on m machines, we provide 2-approximation using poly(d,m) memory.

We designed a φ-competitive deterministic algorithm for bounded-delay packet scheduling. In this 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. Our algorithm is based on the plan which is the maximum-weight subset of pending packets that can be scheduled starting from the current slot.

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 design a 1-pass deterministic streaming algorithms for bin packing and vector scheduling. For bin packing, our streaming approximation scheme uses quantile summaries and interestingly, the connection between streaming bin packing and quantile summaries goes also in the other direction. That is, given a streaming algorithm for bin packing, we can estimate the rank of an item in the stream in the same space, which basically suffices to construct a quantile summary. For vector scheduling in dimension d on m machines, we provide 2-approximation using poly(d,m) memory.

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. In this paper we study several special variants of the problem, namely, (1) we provide an optimal algorithm for the Single-Phase variant, which was used to contruct lower bounds, (2) we study MLAP on paths, where we prove that 4 is the optimal competitive ratio for the deadline variant. Additionally, we provide results on the offline version. All results are covered in the arXiv preprint of the conference version.

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.

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.