Competitiveness

For request sequence Ρ = r¹,r²,... consider

cost_Λ(Ρ): the cost on Ρ achieved by the servers of our online algorithm Λ

cost_opt(Ρ): the cost on Ρ achieved by the server of an optimal offline algorithm

We say that a [randomized] algorithm is C-competitive if for each sequence Ρ we have

E cost_Λ(Ρ) ≤ C. cost_opt(Ρ) + λ

where λ depends only on the initial configuration