**Tight Lower Bound for Comparison-Based Quantile Summaries**

with Graham Cormode.

ArXiv preprint.
View/hide summary.
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.

**Streaming Algorithms for Bin Packing and Vector Scheduling**

with Graham Cormode.

In *WAOA 2019*, LNCS 11926, p. 72-88, Springer, 2020.
ArXiv preprint.
View/hide summary.
WAOA slides.
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.

**A φ-Competitive Algorithm for Scheduling Packets with Deadlines**

with Marek Chrobak, Łukasz Jeż, Jiří Sgall.

In *SODA 2019*, p. 123-142, Society for Industrial and Applied Mathematics, 2019.
doi:10.1137/1.9781611975482.9

ArXiv preprint. Slides for DIMAP seminar (longer).
SODA slides (shorter).
View/hide summary.
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.

**Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices**

with Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop, Tomáš Masařík, and Tomáš Toufar.

In *STACS 2018*, LIPIcs, p. 26:1--26:15, Schloss Dagstuhl, 2018.
LIPIcs link.
ArXiv preprint. View/hide summary.
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.

**On Packet Scheduling with Adversarial Jamming and Speedup**

with Martin Böhm, Łukasz Jeż, Jiří Sgall.

In *WAOA 2017*, LNCS 10787, p. 190-206, Springer, 2018.
ArXiv preprint.
WAOA slides. View/hide summary.
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.

**Online Chromatic Number is PSPACE-Complete**

with Martin Böhm.

In *IWOCA 2016*, LNCS 9843, p. 16-28, Springer, 2016.

**Best Student Paper of IWOCA 2016.**
ArXiv preprint.
HALG 2017 poster. View/hide summary.
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).

**Online Packet Scheduling with Bounded Delay and Lookahead**

with Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall.

In *ISAAC 2016*, LIPIcs, p. 21:1--21:13, Schloss Dagstuhl, 2016.
LIPIcs link, ArXiv preprint.
MAPSP slides. View/hide summary.
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.

**Online Algorithms for Multi-Level Aggregation.**

with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang.

In *ESA 2016*, Leibniz International Proceedings in Informatics (LIPIcs), p. 12:1-12:17, Schloss Dagstuhl, 2016.
LIPIcs link, ArXiv preprint. View/hide summary.
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.

**Better algorithms for online bin stretching**

with Martin Böhm, Jiří Sgall, Rob van Stee.

In *WAOA 2014*, LNCS 8952, p. 236-247, Springer, 2015.
ArXiv preprint. View/hide summary.
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.

**Online colored bin packing**

with Martin Böhm, Jiří Sgall.

In *WAOA 2014*, LNCS 8952, p. 35-46, Springer, 2015.
ArXiv preprint. View/hide summary.
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.

**WALTZ: a strong Tzaar-playing program**

with Tomáš Valla.

In *Computer Games*, CCIS 408, p. 81–96, Springer, 2014. View/hide summary.
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.