The performance of the Multi-Level Feedback algorithm using the novel approach of smooth analysis was analyzed. As such, smooth competitive analysis provides a unifying framework for worst case and average case analysis of online algorithms. This paper considers several smoothening models, including the additive symmetric one, which adapts to the case the model introduced by Spielman and Teng.
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm / Becchetti, Luca; Leonardi, Stefano; MARCHETTI SPACCAMELA, Alberto; Guido, Schaefer; Tjark, Vredeveld. - STAMPA. - (2003), pp. 462-471. (Intervento presentato al convegno 44th Annual IEEE Symposium on Foundations of Computer Science tenutosi a Cambridge, MA; USA nel 11-14 October 2003) [10.1109/SFCS.2003.1238219].
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
BECCHETTI, Luca;LEONARDI, Stefano;MARCHETTI SPACCAMELA, Alberto;
2003
Abstract
The performance of the Multi-Level Feedback algorithm using the novel approach of smooth analysis was analyzed. As such, smooth competitive analysis provides a unifying framework for worst case and average case analysis of online algorithms. This paper considers several smoothening models, including the additive symmetric one, which adapts to the case the model introduced by Spielman and Teng.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
