Source author record

Rob van Stee

Rob van Stee appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory

Catalog footprint

What is connected

6works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

A Two-Phase Algorithm for Bin Stretching with Stretching Factor 1.5

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 the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any number of bins. We build on previous algorithms and use a two-phase approach. However, our analysis is technically more complicated and uses amortization over the bins with the help of two weight functions.

preprint2016arXiv

Online Bin Stretching with Three Bins

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 the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for Online Bin Stretching with a stretching factor of $11/8 = 1.375$ for three bins. Additionally, we present a lower bound of $45/33 = 1.\overline{36}$ for Online Bin Stretching on three bins and a lower bound of $19/14$ for four and five bins that were discovered using a computer search.

preprint2015arXiv

Online Algorithms with Advice for Bin Packing and Scheduling Problems

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 problems, to arbitrarily approach a competitive ratio of $1$ with only a constant number of bits of advice per request. For the bin packing problem, we give an online algorithm with advice that is $(1+\varepsilon)$-competitive and uses $O\left(\frac{1}{\varepsilon}\log \frac{1}{\varepsilon} \right)$ bits of advice per request. For scheduling on $m$ identical machines, with the objective function of any of makespan, machine covering and the minimization of the $\ell_p$ norm, $p >1$, we give similar results. We give online algorithms with advice which are $(1+\varepsilon)$-competitive ($(1/(1-\varepsilon))$-competitive for machine covering) and also use $O\left(\frac{1}{\varepsilon}\log \frac{1}{\varepsilon} \right)$ bits of advice per request. We complement our results by giving a lower bound showing that for any online algorithm with advice to be optimal, for any of the above scheduling problems, a non-constant number (namely, at least $\left(1 - \frac{2m}{n}\right)\log m$, where $n$ is the number of jobs and $m$ is the number of machines) of bits of advice per request is needed.

preprint2012arXiv

A unified approach to truthful scheduling on related machines

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 machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the l_p norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it. The key idea of our novel method is to show that for goal functions that are sufficiently well-behaved functions of the machine loads, it is possible to compute in polynomial time a highly structured nearly optimal schedule. Monotone approximation schemes have an important role in the emerging area of algorithmic mechanism design. In the game-theoretical setting of these scheduling problems there is a social goal, which is one of the objective functions that we study. Each machine is controlled by a selfish single-parameter agent, where its private information is its cost of processing a unit sized job, which is also the inverse of the speed of its machine. Each agent wishes to maximize its own profit, defined as the payment it receives from the mechanism minus its cost for processing all jobs assigned to it, and places a bid which corresponds to its private information. For each one of the problems, we show that we can calculate payments that guarantee truthfulness in an efficient manner. Thus, there exists a dominant strategy where agents report their true speeds, and we show the existence of a truthful mechanism which can be implemented in polynomial time, where the social goal is approximated within a factor of 1+epsilon for every epsilon>0.

preprint2012arXiv

The Price of Anarchy for Selfish Ring Routing is Two

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 much less understood than the average latency. We show that the price of anarchy is at most two, when the network is a ring and the link latencies are linear. Our bound is tight. This is the first sharp bound for the maximum latency objective.

preprint2010arXiv

The Sorting Buffer Problem is NP-hard

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 a random-access buffer of limited capacity which can be used to rearrange items. The problem is to design a scheduling strategy that decides upon the order in which items from the buffer are sent to the server. Each type change incurs unit cost, and thus, the cost minimizing objective is to minimize the total number of type changes for serving the entire sequence. This problem is motivated by various applications in manufacturing processes and computer science, and it has attracted significant attention in the last few years. The main focus has been on online competitive algorithms. Surprisingly little is known on the basic offline problem. In this paper, we show that the sorting buffer problem with uniform cost is NP-hard and, thus, close one of the most fundamental questions for the offline problem. On the positive side, we give an O(1)-approximation algorithm when the scheduler is given a buffer only slightly larger than double the original size. We also give a dynamic programming algorithm for the special case of buffer size two that solves the problem exactly in linear time, improving on the standard DP which runs in cubic time.