Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Smoothening Helps: A Probabilistic Analysis of the Multi-Level Feedback Algorithm

Please always quote using this URN: urn:nbn:de:0297-zib-7366
  • In this paper we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by [{\sl Spielman and Teng} STOC 2001] to explain the behaviour 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 Multi-Level Feedback (MLF) algorithm 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. The initial processing times are integers in the range $[1,2^K]$. We use a partial bit randomization model, where the initial processing times are smoothened by changing the $k$ least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of $O(max((2^k/\sigma)^3, (2^k/\sigma)^2 2^K-k))$, where $\sigma$ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of $O(2^K-k)$ if $\sigma = \Theta(2^k)$. %The analysis holds for an oblivious as well as for a stronger adaptive %adversary. We also prove an $\Omega(2^{K-k})$ lower bound for any deterministic algorithm that is run on processing times smoothened according to the partial bit randomization model. For various other smoothening models, including the additive symmetric smoothening model used by [{\sl Spielman and Teng}], we give a higher lower bound of $\Omega(2^K)$. A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform distribution.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, Tjark Vredeveld
Document Type:ZIB-Report
Tag:competitive analysis; scheduling; smoothed analysis
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Mxx Computer system organization / 68M20 Performance evaluation; queueing; scheduling [See also 60K25, 90Bxx]
Date of first Publication:2003/05/23
Series (Serial Number):ZIB-Report (03-14)
ZIB-Reportnumber:03-14
Published in:Appeared in: "Average case and smoothed competitive analysis for the multi-level feedback algorithm", Proc. of the 44th Annual IEEE Symp. on Fundations of Computer Science (FOCS) 462-471 (2003)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.