Topology matters: Smoothed competitiveness of metrical task systems

We also provide the first average case analysis of WFA. We prove that WFA has O(log(Δ)) expected competitive ratio if the request costs are chosen randomly from an arbitrary non-increasing distribution with standard deviation σ=Θ(λmin).