Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, II piano
Aula C2

Abstract:
Spielman and Teng invented the concept of smoothed analysis to explain the success of algorithms that are known to work well in practice while presenting poor worst case performance. Spielman and Teng [STOC 01] proved that the simplex algorithm runs in expected polynomial time if the input instance is smoothened with a normal distribution.

We extend this notion to analyze online algorithms. In particular we introduce smoothed competitive analysis to study the Multi-Level Feedback (MLF) algorithm, at the basis of the scheduling policies of Unix and Windows NT, when the processing times of jobs released over time are only known at time of completion.

We show that, if the k least significant of K bits describing the processing time of a job are randomly changed, MLF achieves a tight smoothed competitive ratio of O(2^{K-k}) to minimize the average flow time. A direct consequence is a first constant approximation for this problem in the average case under a quite general class of probability distributions.

Joint work with L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, T. Vredeveld