A Bicriteria Approximation for the Reordering Buffer Problem

Details A Bicriteria Approximation for the Reordering Buffer Problem A Bicriteria Approximation for the Reordering Buffer Problem

2012-04-26

arxiv.org/abs/1204.5823v1

Computer Science

Data Structures and Algorithms

13 pages

Scientific paper

In the reordering buffer problem (RBP), a server is asked to process a sequence of requests lying in a metric space. To process a request the server must move to the corresponding point in the metric. The requests can be processed slightly out of order; in particular, the server has a buffer of capacity k which can store up to k requests as it reads in the sequence. The goal is to reorder the requests in such a manner that the buffer constraint is satisfied and the total travel cost of the server is minimized. The RBP arises in many applications that require scheduling with a limited buffer capacity, such as scheduling a disk arm in storage systems, switching colors in paint shops of a car manufacturing plant, and rendering 3D images in computer graphics. We study the offline version of RBP and develop bicriteria approximations. When the underlying metric is a tree, we obtain a solution of cost no more than 9OPT using a buffer of capacity 4k + 1 where OPT is the cost of an optimal solution with buffer capacity k. Constant factor approximations were known previously only for the uniform metric (Avigdor-Elgrabli et al., 2012). Via randomized tree embeddings, this implies an O(log n) approximation to cost and O(1) approximation to buffer size for general metrics. Previously the best known algorithm for arbitrary metrics by Englert et al. (2007) provided an O(log^2 k log n) approximation without violating the buffer constraint.

Affiliated with

Also associated with

No associations

Rating

A Bicriteria Approximation for the Reordering Buffer Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Bicriteria Approximation for the Reordering Buffer Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Bicriteria Approximation for the Reordering Buffer Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-313621