19 citations · 25 across the 3 of their papers we have counts for
11 papers
Structural Properties of Search Trees with 2-way Comparisons
Sunny Atalig, Marek Chrobak, Erfan Mousavian +2
Optimal 3-way comparison search trees (3WCST's) can be computed using standard dynamic programming in time O(n^3), and this can be further improved to O(n^2) by taking advantage of…
Streaming Algorithms for Bin Packing and Vector Scheduling
Graham Cormode, Pavel Veselý
Problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling, are fundamental tasks in combinatorial optimization. These are w…
A Tight Lower Bound for Comparison-Based Quantile Summaries
Graham Cormode, Pavel Veselý
Quantiles, such as the median or percentiles, provide concise and useful information about the distribution of a collection of items, drawn from a totally ordered universe. We stud…
A -Competitive Algorithm for Scheduling Packets with Deadlines
Pavel Veselý, Marek Chrobak, Łukasz Jeż +1
In the online packet scheduling problem with deadlines (PacketSchD, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need…
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop +3
We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensive…
On Packet Scheduling with Adversarial Jamming and Speedup
Martin Böhm, Łukasz Jeż, Jiří Sgall +1
In Packet Scheduling with Adversarial Jamming packets of arbitrary sizes arrive over time to be transmitted over a channel in which instantaneous jamming errors occur at times chos…