M.Sc Thesis

M.Sc StudentLaserson Jonathan
SubjectApproximations Algorithms for Sorting Buffers
DepartmentDepartment of Computer Science
Supervisor PROFESSOR EMERITUS Reuven Bar-Yehuda


    The Sorting Buffers problem is motivated by many applications in manufacturing processes and computer science, among them car-painting and file-servers architecture. The input is a sequence of items of various types. All the items must be processed, one by one, by a service station. We are given a random-access sorting buffer with a limited capacity.  Whenever a new item arrives it may be moved directly to the service station or stored in the buffer.  Also, at any time items can be removed from the buffer and assigned to the service station.  Our goal is to give the service station a sequence of items with minimum type transitions.

    We present a polynomial time 9-approximation algorithm for the maximization variant of this problem.  This result improves the best previously known 20-approximation algorithm.  In the maximization variant, the goal is to maximize the number of times an item at the service station is followed by another item of the same type.  To obtain our result we generalize the problem further.  We allow items to have different sizes, and also assign each item a profit which is gained only if the following item has the same type (setting the goal to maximize the profit).  We prove some combinatorial lemmas about the optimal solutions for this problem, and apply the Local-Ratio Technique to obtain our approximation algorithm.   We also give a (7+2/m)-approximation for another generalization in which we are allowed to use $m$ buffers of the same capacity.