A universal randomized packed scheduling algorithm

0397213 - MÚ 2014 RIV US eng J - Journal Article
Jeż, Łukasz
A universal randomized packed scheduling algorithm.
Algorithmica. Roč. 67, č. 4 (2013), s. 498-515. ISSN 0178-4617. E-ISSN 1432-0541
R&D Projects: GA AV ČR IAA100190902
Institutional support: RVO:67985840
Keywords : online algorithms * competitive analysis * adaptive adversary
Subject RIV: BA - General Mathematics
Impact factor: 0.567, year: 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.
Permanent Link: http://hdl.handle.net/11104/0224827