首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Randomized Algorithm for Agreeable Deadlines Packet Scheduling
  • 作者:Lukasz Jez
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2010
  • 卷号:5
  • 页码:489-500
  • DOI:10.4230/LIPIcs.STACS.2010.2479
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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{Hajek-det-lb}. 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.
  • 关键词:Online algorithms; scheduling; buffer management
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有