Realtime Scheduling, Bin Packing and Directed Diophantine Approximation<BR>

<p>
 <BR>
Friedrich Eisenbrand, EPFL<BR>

<P>
Abstract:<BR>

This talk deals with  the popular fixed priority realtime scheduling problem, which was introduced 
by Liu and Layland more than 35 years ago. This problem has received a lot of attention in the 
realtime-systems community (the paper of  Liu and Layland  is today ranked second on the 
citeseer list of most cited cs-papers). 

<p>
We will look at this problem from an algorithmic  perspective and outline several results concerning 
approximability and complexity which reveal themselves via connections of of this problem to bin-packing 
and simultaneous diophantine approximation. 

<p>
Joint work with Thomas Rothvoss