We consider the (
preemptive bipartite scheduling problem PBS) (Crescenzi et al.,
2 - \frac1d+12 - \frac{1}{d+1}
approximation algorithm, which is the first one for the PBS problem with approximation ratio strictly less than two. Furthermore, we propose a simple optimal polynomial time algorithm for a subclass of instances of the PBS problem.
Keywords switching networks - scheduling - set-up delays - approximation algorithms
This work has been partially supported by the the European Union (FET-Working Group APPOL II), and the Greek General Secretariat of Research and Technology.