Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm

DOI10.1287/moor.1050.0170zbMath1278.90143OpenAlexW2141156389MaRDI QIDQ5387966

Luca Becchetti, Tjark Vredeveld, Alberto Marchetti-Spaccamela, Guido Schäfer, Stefano Leonardi

Publication date: 27 May 2008

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.1050.0170

zbMATH Keywords

schedulingcompetitive analysisaverage-case analysismultilevel feedback

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (13)

Smoothed analysis of binary search trees ⋮ Smoothed Analysis of Local Search Algorithms ⋮ Evaluating the quality of online optimization algorithms by discrete event simulation ⋮ On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis ⋮ Smoothed performance guarantees for local search ⋮ Average-case competitive analyses for one-way trading ⋮ Beyond the worst case: semi-random complexity analysis of winner determination ⋮ On smoothed analysis of quicksort and Hoare's find ⋮ Computational complexity of kernel-based density-ratio estimation: a condition number analysis ⋮ Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison ⋮ On the smoothness of paging algorithms ⋮ On robust online scheduling algorithms ⋮ Unnamed Item

This page was built for publication: Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm