A Universal Randomized Packet Scheduling Algorithm |
| |
Authors: | Łukasz Jeż |
| |
Affiliation: | 1. Institute of Computer Science, University of Wroc?aw, ul. Joliot-Curie 15, 50-383, Wroc?aw, Poland 2. Institute of Mathematics, Academy of Sciences of the Czech Republic, ?itná 25, 115 67, Praha 1, Czech Republic
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|