# Pavel Veselý

An approximation of my appearance.

A somewhat better approximation.

Welcome to my academic homepage! I'm currently studying doctoral program Discrete Models and Algorithms
at

Computer Science Institute of

Charles University in Prague.
The institute is a part of

Faculty of Mathematics and Physics.
My advisor is professor

Jiří Sgall
and I'm also working a lot with his other Ph.D. student

Martin Böhm.

## News

- 17. 7. 2018: The thesis is finally submitted together with a new paper on bounded-delay packet scheduling
containing a φ-competitive algorithm!

## Contact

- Email: <last name> (at) iuuk.mff.cuni.cz
- I'm usually sitting in room S320.

## Teaching / Výuka

### LS 17/18

### ZS 17/18 (winter semester 17/18)

Teaching in previous years (in Czech only) / Výuka v předchozích letech

## Research interests

- Approximation and online algorithms, mostly some variants of scheduling and bin packing.
- Techniques for designing approximation algorithms, mainly linear and semidefinite programming.
- Fixed parameter tractable (FPT) algorithms, in particular FPT approximation.

## Projects

Selected work (see also publications below):

Recent collaborators (except J. Sgall, M. Böhm and our local FPT group):

## Publications

Papers are ordered basically from the newest to the oldest and each has a short summary.
See also my

ORCID account,

Google Scholar account,
or

dblp search.

### Conference papers

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

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

Submitted .
ArXiv preprint. 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.

### Journal papers

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

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

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

Submitted.
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 Packet Scheduling with Bounded Delay and Lookahead**

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

Submitted. 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 Chromatic Number is PSPACE-Complete**

with Martin Böhm.

*Theory of Computing Systems*, vol. 62(6), p. 1366–1391, Springer, 2017,
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).

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

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

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

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

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

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

## Recommended books, articles, videos etc., mosly about personal development

- Course
*Learning how to learn* –
we are learning for 13-18 years, but has anybody ever told us *how* to do it effectively? Besides learning, they discuss some mind tricks for problem solving.
*The end of procrastination* (in Czech “Konec prokrastinace”) – a book not only about how to tackle procrastination,
but also about motivation, effective time planning, heroism (in the ordinary life) and objectivity.
In English it should be available soon if not already now.
Czech web page.
*GrowJob institute* – a company that offers lectures or workshops (in Czech) or personal consultations on personal development,
such as tackling procrastination (the speaker is the author of the above mentioned book), satisfaction, focus etc. They also have some articles and videos in Czech on their webpage.
*ChiRunning* – a book about *how* to run (based on T’ai Chi).

## Other stuff (life, the Universe and everything)

See (future) personal page.