One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay

Details One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay

2011-02-07

arxiv.org/abs/1102.1273v1

Computer Science

Data Structures and Algorithms

14 pages

Scientific paper

We give a memoryless scale-invariant randomized algorithm for the Buffer Management with Bounded Delay problem that is e/(e-1)-competitive against an adaptive adversary, together with better performance guarantees for many restricted variants, including the s-bounded instances. In particular, our algorithm attains the optimum competitive ratio of 4/3 on 2-bounded instances. Both the algorithm and its analysis are applicable to a more general problem, called Collecting Items, in which only the relative order between packets' deadlines is known. Our algorithm is the optimal randomized memoryless algorithm against adaptive adversary for that problem in a strong sense. While some of provided upper bounds were already known, in general, they were attained by several different algorithms.

Affiliated with

Also associated with

No associations

Rating

One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay 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 One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-681040