We consider scheduling of colored packets with transition costs which form a general metric space. We design a @math competitive algorithm. Our main result is a hardness result of @math which matches the competitive ratio of the algorithm for each metric space separately. In particular, we improve the hardness result of Azar at el. 2009 for uniform metric spaces. We also extend our result to weighted directed graphs which obey the triangular inequality and show a @math competitive algorithm and a nearly-matching hardness result. In proving our hardness results we use some interesting non-standard embedding.
@cite_13: An instance of the sorting buffer problem consists of a metric space and a server, equipped with a finite-capacity buffer capable of holding a limited number of requests. An additional ingredient of the input is an online sequence of requests, each of which is characterized by a destination in the given metric; whenever a request arrives, it must be stored in the sorting buffer. At any point in time, a currently pending request can be served by drawing it out of the buffer and moving the server to its corresponding destination. The objective is to serve all input requests in a way that minimizes the total distance traveled by the server. In this paper, we focus our attention on instances of the problem in which the underlying metric is either an evenly-spaced or a continuous line metric. Our main findings can be briefly summarized as follows: 1. We present a deterministic O(log n) competitive algorithm for n- point evenly-spaced line metrics. This result improves on a randomized O(log2 n) competitive algorithm due to Khandekar and Pandit. 2. We devise a deterministic O(log N log log N) competitive algorithm for continuous line metrics, where N is the input sequence length. 3. We establish the first non-trivial lower bound for the evenly-spaced case, by proving that the competitive ratio of any deterministic algorithm is at least 2+√3 √3 ≅ 2.154.
@cite_14: 
@cite_9: We study the behavior of algorithms for buffering packets weighted by different levels of Quality of Service (QoS) guarantees in a single queue. Buffer space is limited, and packet loss occurs when the buffer overflows. We describe a modification of the previously proposed “preemptive greedy” algorithm of for buffer management and give an analysis to show that this algorithm achieves a competitive ratio of at most 1.75. This improves upon recent work showing a 1.98 competitive ratio, and a previous result that shows a simple greedy algorithm has a competitive ratio of 2.
@cite_29: We consider the online scheduling problem for sorting buffers on a line metric, motivated by an application to disc scheduling. Input is an online sequence of requests. Each request is a block of data to be written on a specified track of the disc. To write a block on a particular track, the scheduler has to bring the disc head to that track. The cost of moving the disc head from a track to another is the distance between those tracks. A sorting buffer that can store at most k requests at a time is available to the scheduler. This buffer can be used to rearrange the input sequence. The objective is to minimize the total cost of head movement while serving the requests. On a disc with n uniformly-spaced tracks, we give a randomized online algorithm with a competitive ratio of O(log2n) in expectation against an oblivious adversary. We show that any deterministic strategy which makes scheduling decisions based only on the contents of the buffer has a competitive ratio of Ω(k) or Ω(log n loglog n).
@cite_6: We consider a network providing Differentiated Services (Diffserv) which allow Internet service providers (ISP) to offer different levels of Quality of Service (QoS) to different traffic streams. We study FIFO buffering algorithms, where packets must be transmitted in the order they arrive. The buffer space is limited, and packets are lost if the buffer is full. Each packet has an intrinsic value, and the goal is to maximize the total value of transmitted packets. Our main contribution is an algorithm for arbitrary packet values that for the first time achieves a competitive ratio better than 2, namely 2-e for a constant e> 0.
@cite_0: We consider the online problem of active queue management. In our model, the input is a sequence of packets with values v ∈ [1,α] that arrive to a queue that can hold up to B packets. Specifically, we consider a FIFO non-preemptive queue, where any packet that is accepted into the queue must be sent, and packets are sent by the order of arrival. The benefit of a scheduling policy, on a given input, is the sum of values of the scheduled packets. Our aim is to find an online policy that maximizes its benefit compared to the optimal offline solution.
@cite_27: 
@cite_23: 
@cite_15: 
@cite_10: We consider the online problem of non-preemptive queue management. An online sequence of packets arrive, each of which has an associated intrinsic value. Packets can be accepted to a FIFO queue, or discarded. The profit gained by transmitting a packet diminishes over time and is equal to its value minus the delay. This corresponds to the well known and strongly motivated Naor's model in operations research. We give a queue management algorithm with a competitive ratio equal to the golden ratio (φ a 1.618) in the case that all packets have the same value, along with a matching lower bound. We also derive Θ(1) upper and lower bounds on the competitive ratio when packets have different intrinsic values (in the case of differentiated services). We can extend our results to deal with more general models for loss of value over time. Finally, we re-interpret our online algorithms in the context of selfish agents, producing an online mechanism that approximates the optimal social welfare to within a constant factor.
@cite_25: 
@cite_12: 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 generalize the problem to allow items with different sizes and type transitions with different costs. We give a polynomial-time 9-approximation algorithm for the maximization variant of this problem, which improves the best previously known 20-approximation algorithm.
In the FIFO queue model @cite_14 we are given a sequence of incoming packets. The packets are placed in a FIFO queue with bounded buffer size. The challenges for an online algorithm are to decide whether to accept or discard arriving packet, and to choose a queue for transmission in each time unit. The problem was studied in @cite_0 @cite_9 @cite_6 @cite_27 @cite_10 . Another related problem is the sorting buffer problem @cite_15 . In that problem we are given a server with unbounded capacity and an incoming sequence of requests. Each request corresponds to a point in a metric space. The goal is to serve all requests while minimizing the total distance traveled by the server. This problem can be interpreted as a multi-port device problem. This model was studied in @cite_25 @cite_29 @cite_12 @cite_13 @cite_23 .