Jez, Lukasz
Randomized Algorithm for Agreeable Deadlines Packet Scheduling
Abstract
In 2005 Li~et~al. gave a \(\phi\)competitive deterministic online algorithm for scheduling of packets with agreeable deadlines~\cite{DBLP:conf/soda/LiSS05} with a very interesting analysis. This is known to be optimal due to a lower bound by Hajek~\cite{Hajekdetlb}. 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 (\frac{4}{3}\). Note that this still leaves a gap between the best known lower bound of \(\frac{5}{4}\) by Chin~et~al.~\cite{DBLP:journals/algorithmica/ChinF03} for randomized algorithms against oblivious adversary.
BibTeX  Entry
@InProceedings{jez:LIPIcs:2010:2479,
author = {Lukasz Jez},
title = {{Randomized Algorithm for Agreeable Deadlines Packet Scheduling}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {489500},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2479},
URN = {urn:nbn:de:0030drops24795},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2479},
annote = {Keywords: Online algorithms, scheduling, buffer management}
}
2010
Keywords: 

Online algorithms, scheduling, buffer management 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Related Scholarly Article: 


Issue date: 

2010 
Date of publication: 

2010 