50 citations · 64 across the 7 of their papers we have counts for
10 papers
Forwarding Packets Greedily on the Line
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen +2
We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its…
The Buffer Minimization Problem for Scheduling Flow Jobs with Conflicts
Niklas Haas, Sören Schmitt, Rob van Stee
We consider the online buffer minimization in multiprocessor systems with conflicts problem (in short, the buffer minimization problem) in the recently introduced flow model. In an…
Minimizing the Weighted Makespan with Restarts on a Single Machine
Aflatoun Amouzandeh, Klaus Jansen, Lis Pirotton +2
We consider the problem of minimizing the weighted makespan on a single machine with restarts. Restarts are similar to preemptions but weaker: a job can be interrupted, but then it…
Improved online load balancing with known makespan
Martin Böhm, Matej Lieskovský, Sören Schmitt +2
We break the barrier of for the problem of online load balancing with known makespan, also known as bin stretching. In this problem, identical machines and the optimal ma…
Improved Lower Bounds for Online Hypercube and Rectangle Packing
David Blitz, Sandy Heydrich, Rob van Stee +2
Packing a given sequence of items into as few bins as possible in an online fashion is a widely studied problem. We improve lower bounds for packing boxes into bins in two or more…
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…
Beating the Harmonic lower bound for online bin packing
Sandy Heydrich, Rob van Stee
In the online bin packing problem, items of sizes in (0,1] arrive online to be packed into bins of size 1. The goal is to minimize the number of used bins. In this paper, we presen…
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 Algorithms with Advice for Bin Packing and Scheduling Problems
Marc P. Renault, Adi Rosén, Rob van Stee
We consider the setting of online computation with advice, and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these prob…
A unified approach to truthful scheduling on related machines
Leah Epstein, Asaf Levin, Rob van Stee
We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTAS's) for a wide class of scheduling problems on uniformly related mach…