A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines

Łukasz Jeż 1, *
* Auteur correspondant
Abstract : 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.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.489-500, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00455740
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 09:49:52
Dernière modification le : jeudi 11 février 2010 - 09:57:31
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:08:41

Fichier

jez-lukasz.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455740, version 1

Collections

Citation

Łukasz Jeż. A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.489-500, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455740〉

Partager

Métriques

Consultations de la notice

118

Téléchargements de fichiers

64