| Article ID: | iaor200924266 |
| Country: | United States |
| Volume: | 31 |
| Issue: | 1 |
| Start Page Number: | 85 |
| End Page Number: | 108 |
| Publication Date: | Feb 2006 |
| Journal: | Mathematics of Operations Research |
| Authors: | Vredeveld Tjark, Leonardi Stefano, Becchetti Luca, MarchettiSpaccamela Alberto, Schfer Guido |
In this paper, we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng to explain the behavior of algorithms that work well in practice while performing very poorly from a worst–case analysis point of view. We apply this notion to analyze the multilevel feedback algorithm (MLF) to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion.