Can I read Online Scheduling of Packets with Agreeable Deadlines on EtoBox?

Online Scheduling of Packets with Agreeable Deadlines by Łukasz Jeż; Fei Li; Jay Sethuraman; Clifford Stein is a Computer Science article available to read on EtoBox.

What is Online Scheduling of Packets with Agreeable Deadlines about?

This article concerns an online packet scheduling problem that arises as a natural model for buffer management at a network router. Packets arrive at a router at integer time steps, and are buffered upon arrival. Packets have non-negative weights and integer deadlines that are (weakly) increasing in their arrival times. In each integer time step, at most one packet can be sent. The objective is to maximize the sum of the weights of the packets that are sent by their deadlines. The main results include an optimal (φ := (1 + √ 5)/2 ≈ 1.618)-competitive deterministic online algorithm, a (4/3 ≈ 1.33)-competitive randomized online algorithm against an oblivious adversary, and a 2-speed 1-competitive deterministic online algorithm. The analysis does not use a potential function explicitly, but instead modifies the adversary's buffer and credits the adversary to account for these modifications.

Who reads Online Scheduling of Packets with Agreeable Deadlines?

Author

Łukasz Jeż; Fei Li; Jay Sethuraman; Clifford Stein

Publisher

ACM

Published

2012

Language

EN

Field

Computer Science (Physical Sciences)