A constant approximation algorithm for sorting buffers

Jens S. Kohrt and Kirk Pruhs. A constant approximation algorithm for sorting buffers. In Proceedings of the Sixth Latin American Symposium (LATIN 2004), volume 2976 of Lecture Notes in Computer Science, pages 193-202. Springer-Verlag, 2004.
We consider an algorithmic problem that arises in manufacturing applications. The input is a sequence of objects of various types. The scheduler is fed the objects in the sequence one by one, and is equipped with a finite buffer. The goal of the scheduler/sorter is to maximally reduce the number of type transitions. We give the first polynomial-time constant approximation algorithm for this problem.

We prove several lemmas about the combinatorial structure of optimal solutions that may be useful in future research, and we show that the unified algorithm based on the local ratio lemma performs well for a slightly larger class of problems than was apparently previously known.

This paper is © Springer-Verlag.
Available as ps (282 KB), ps.gz (130 KB), and pdf (146 KB).
Also available at SpringerLink.
The slides of my talk are available as ps (587 KB), ps.gz (52 KB), and pdf (1056 KB).
Related Papers:

See also other papers by Jens Svalgaard Kohrt.