Computer Science – Data Structures and Algorithms
Scientific paper
2009-05-25
Computer Science
Data Structures and Algorithms
11 pages, 3-4 figures; new version due to STACS submission
Scientific paper
In 2005 Li et al. gave a phi-competitive deterministic online algorithm for scheduling of packets with agreeable deadlines with a very interesting analysis. This is known to be optimal due to a lower bound by Hajek. We claim that the algorithm by Li et al. can be slightly simplified, while retaining its competitive ratio. Then we introduce randomness to the modified algorithm and argue that the competitive ratio against oblivious adversary is at most 4/3. Note that this still leaves a gap between the best known lower bound of 5/4 by Chin et al. for randomised algorithms against oblivious adversary.
No associations
LandOfFree
A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines 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 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-294873