Result: A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines
Title:
A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines
Authors:
Contributors:
Institute of Computer Science, University of Wrocław [Poland] (UWr), Inria Nancy Grand Est & Loria, Jean-Yves Marion and Thomas Schwentick
Source:
27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010. :489-500
Publisher Information:
HAL CCSD, 2010.
Publication Year:
2010
Collection:
collection:STACS2010
Subject Terms:
Subject Geographic:
Original Identifier:
HAL:
Document Type:
Conference
conferenceObject<br />Conference papers
Language:
English
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00455740v1
Database:
HAL
Further Information
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.