10 citations · 13 across the 5 of their papers we have counts for
5 papers
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…
The Sorting Buffer Problem is NP-hard
Ho-Leung Chan, Nicole Megow, Rob van Stee +1
We consider the offline sorting buffer problem. The input is a sequence of items of different types. All items must be processed one by one by a server. The server is equipped with…
An Absolute 2-Approximation Algorithm for Two-Dimensional Bin Packing
Rolf Harren, Rob van Stee
We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of bins used. All rectangles have to be packed non-overlappi…
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…
Covering selfish machines
Leah Epstein, Rob van Stee
We consider the machine covering problem for selfish related machines. For a constant number of machines, m, we show a monotone polynomial time approximation scheme (PTAS) with run…