Publications (15)
Improved results for a memory allocation problem
Leah Epstein, Rob van Stee
We consider a memory allocation problem that can be modeled as a version of bin packing where items may be split, but each bin may contain at most two (parts of) items. A 3/2-appro…
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…
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…
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…
The Price of Anarchy for Selfish Ring Routing is Two
Xujin Chen, Benjamin Doerr, Xiaodong Hu +3
We analyze the network congestion game with atomic players, asymmetric strategies, and the maximum latency among all players as social cost. This important social cost function is…
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…