A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

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

Résumé

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.
Fichier principal
Vignette du fichier
jez-lukasz.pdf (215.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00455740 , version 1 (11-02-2010)

Identifiants

  • HAL Id : inria-00455740 , version 1

Citer

Łukasz Jeż. A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.489-500. ⟨inria-00455740⟩

Collections

STACS2010
46 Consultations
49 Téléchargements

Partager

Gmail Facebook X LinkedIn More