4 papers · 1 filter
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…