3 citations · 5 across the 6 of their papers we have counts for
14 papers · 1 filter
Two Complexity Results on Spanning-Tree Congestion Problems
Sunny Atalig, Marek Chrobak, Christoph Dürr +4
In the spanning-tree congestion problem (), we are given a graph , and the objective is to compute a spanning tree of that minimizes the maximum edge congestio…
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
Mateusz Basiak, Marcin Bienkowski, Martin Böhm +4
We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the ``standard'' model, in which an algorithm is allowed to swap the requ…
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…
Improved Analysis of Online Balanced Clustering
Marcin Bienkowski, Martin Böhm, Martin Koutecký +3
In the online balanced graph repartitioning problem, one has to maintain a clustering of nodes into clusters, each having nodes. During runtime, an online…
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…
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…