A universal randomized packed scheduling algorithm

0397213 - MÚ 2014 RIV US eng J - Článek v odborném periodiku
Jeż, Łukasz
A universal randomized packed scheduling algorithm.
Algorithmica. Roč. 67, č. 4 (2013), s. 498-515. ISSN 0178-4617. E-ISSN 1432-0541
Grant CEP: GA AV ČR IAA100190902
Institucionální podpora: RVO:67985840
Klíčová slova: online algorithms * competitive analysis * adaptive adversary
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.567, rok: 2013
http://link.springer.com/article/10.1007%2Fs00453-012-9700-0

We give a memoryless scale-invariant randomized algorithm ReMix for Packet Scheduling that is e/(e−1)-competitive against an adaptive adversary. ReMix unifies most of previously known randomized algorithms, and its general analysis yields improved performance guarantees for several restricted variants, including the s-bounded instances. In particular, ReMix attains the optimum competitive ratio of 4/3 on 2-bounded instances. Our results are applicable to a more general problem, called Item Collection, in which only the relative order between packets’ deadlines is known. ReMix is the optimal memoryless randomized algorithm against adaptive adversary for that problem.
Trvalý link: http://hdl.handle.net/11104/0224827