Reordering Buffer Management for Non-uniform Cost Models

摘要

A sequence of objects which are characterized by their color has to be processed. Their processing order influences how efficiently they can be processed: Each color change between two consecutive objects produces non-uniform cost. A reordering buffer which is a random access buffer with storage capacity for k objects can be used to rearrange this sequence in such a way that the total cost are minimized. This concept is useful for many applications in computer science and economics. We show that a reordering buffer reduces the cost of each sequence by a factor of at most 2k - 1. This result even holds for cost functions modeled by arbitrary metric spaces. In addition, a matching lower bound is presented. Prom this bound follows that each strategy that does not increase the cost of a sequence is at least (2k - l)-competitive. As main result, we present the deterministic Maximum Adjusted Penalty (MAP) strategy which is O(log k)-competitive. Previous strategies only achieve a competitive ratio of k in the non-uniform model. For the upper bound on MAP, we introduce a basic proof technique. We believe that this technique can be interesting for other problems.