Pavel Veselý

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

2. Streaming Algorithms for Bin Packing and Vector Scheduling
   with Graham Cormode.
   To appear in WAOA 2019. 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.

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

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

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

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

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

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

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

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

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

Journal papers

1. New Results on 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.
   Submitted. 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. 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.

2. 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.
   Submitted. 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.

3. On Packet Scheduling with Adversarial Jamming and Speedup
   with Martin Böhm, Łukasz Jeż, Jiří Sgall.
   Annals of Operations Research, 2019.
   doi:10.1007/s10479-019-03153-x. 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.

4. Online Packet Scheduling with Bounded Delay and Lookahead
   with Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall.
   In Theoretical Computer Science, vol. 776, p. 95-113, 2019.
   doi:10.1016/j.tcs.2019.01.013. 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.

5. Online Chromatic Number is PSPACE-Complete
   with Martin Böhm.
   Theory of Computing Systems, vol. 62(6), p. 1366–1391, Springer, 2018.
   doi:10.1007/s00224-017-9797-2. 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).

6. Logarithmic price of buffer downscaling on line metrics
   with Marcin Bienkowski, Martin Bohm, Łukasz Jeż, Paweł Laskoś-Grabowski, Jan Marcinkowski, Jiří Sgall, Aleksandra Spyra.
   Theoretical Computer Science, vol. 707, p. 89-93, Elsevier, 2018, doi:10.1016/j.tcs.2017.10.008. ArXiv preprint. View/hide summary.

   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.

7. 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.
   To appear in Operations Research, 2019. 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.

   .
8. A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5
   with Martin Böhm, Jiří Sgall, Rob van Stee.
   Journal of Combinatorial Optimization, vol. 34(3), p. 810-828, Springer, 2017.
   doi:10.1007/s10878-017-0114-4. 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.) 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.

9. Online Bin Stretching with Three Bins
   with Martin Böhm, Jiří Sgall, Rob van Stee.
   Journal of Scheduling, vol. 20(6), p. 601-621, Springer, 2017, doi:10.1007/s10951-016-0504-y. 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.) 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.

10. Colored Bin Packing: Online Algorithms and Lower Bounds
    with Martin Böhm, György Dósa, Leah Epstein, Jiří Sgall.
    Algorithmica, vol. 80(1), p. 155-184, Springer, 2018.
    doi:10.1007/s00453-016-0248-2. 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.