19 citations · 38 across the 6 of their papers we have counts for
12 papers · 1 filter
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…
Logarithmic price of buffer downscaling on line metrics
Marcin Bienkowski, Martin Böhm, Łukasz Jeż +5
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 p…
Online Packet Scheduling with Bounded Delay and Lookahead
Martin Böhm, Marek Chrobak, Łukasz Jeż +3
We study the online bounded-delay packet scheduling problem (BDPS), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each pac…
A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5
Martin Böhm, Jiří Sgall, Rob van Stee +1
Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack t…
Online Algorithms for Multi-Level Aggregation
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka +7
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T t…
Online Bin Stretching with Three Bins
Martin Böhm, Jiří Sgall, Rob van Stee +1
Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack t…
Online Colored Bin Packing
Martin Böhm, Jiří Sgall, Pavel Veselý
In the Colored Bin Packing problem a sequence of items of sizes up to arrives to be packed into bins of unit capacity. Each item has one of colors and an additional c…