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

References

• Alon N., Spencer J. H.The Probabilistic Method (2000) 2nd ed.(Wiley, Chichester, UK) . Wiley-Interscience Series in Discrete MathematicsCrossref, Google Scholar
• Banderier C., Beier R., Mehlhorn K. Smoothed analysis of three combinatorial problems. 28th Internat. Sympos. Math. Foundations Comput. Sci. (2003) (Springer, Berlin, Germany) 198–207LNCS, No. 2747Google Scholar
• Becchetti L., Leonardi S. Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM (2004) 51(4):517–539Crossref, Google Scholar
• Becchetti L., Leonardi S., Marchetti-Spaccamela A., Schäfer G., Vredeveld T. Average case and smoothed competitive analysis of the multi-level feedback algorithm. Proc. 44th Annual IEEE Sympos. Foundations Comput. Sci. (2003) 462–471Google Scholar
• Beier R., Vöcking B. Random knapsack in expected polynomial time. Proc. 35th Annual ACM Sympos. Theory Comput. (2003) 232–241Google Scholar
• Beier R., Vöcking B. Typical properties of winners and losers in discrete optimization. Proc. 36th Annual ACM Sympos. Theory Comput. (2004) 343–352Google Scholar
• Beier R., Czumaj A., Krysta P., Vöcking B. Computing equilibria for congestion games with (im)perfect information. Proc. 15th Annual ACM-SIAM Sympos. Discrete Algorithms (2004) 739–748Google Scholar
• Blum A., Dunagan J. Smoothed analysis of the perceptron algorithm. Proc. 13th Annual ACM-SIAM Sympos. Discrete Algorithms (2002) 905–914Google Scholar
• Borodin A., El-Yaniv R.Online Computation and Competitive Analysis (1998) (Cambridge University Press, New York) Google Scholar
• Borodin A., Irani S., Raghavan P., Schieber B. Competitive paging with locality of reference. J. Comput. System Sci. (1995) 50(2):244–258Crossref, Google Scholar
• Feller W.An Introduction to Probability Theory and Its Applications (1967) (John Wiley & Sons, Inc., New York) Google Scholar
• Grimmett G. R., Stirzaker D. R.Probability and Random Processes (2001) 3rd ed.(Oxford University Press, New York) Google Scholar
• Kalyanasundaram B., Pruhs K. Speed is as powerful as clairvoyance. J. ACM (2000) 47(4):617–643Crossref, Google Scholar
• Kalyanasundaram B., Pruhs K. Minimizing flow time nonclairvoyantly. J. ACM (2003) 50(4):551–567Crossref, Google Scholar
• Koutsoupias E., Papadimitriou C. Beyond competitive analysis. Proc. 25th Sympos. Foundations Comput. Sci. (1994) 394–400Google Scholar
• Leonardi S., Raz D. Approximating total flow time on parallel machines. Proc. 29th Annual ACM Sympos. Theory Comput. (1997) 110–119Google Scholar
• Michel J. E., Coffman E. G. Synthesis of a feedback queueing discipline for computer operation. J. ACM (1974) 21(2):329–339Crossref, Google Scholar
• Motwani R., Raghavan P.Randomized Algorithms (1995) 1st ed.(Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Motwani R., Phillips S., Torng E. Non-clairvoyant scheduling. Theoretical Comput. Sci. (1994) 130:17–47Crossref, Google Scholar
• Nutt G.Operating System Projects Using Windows NT (1999) (Addison-Wesley, Reading, MA) Google Scholar
• Scharbrodt M., Schickinger T., Steger A. A new average case analysis for completion time scheduling. Proc. 34th Annual ACM Sympos. Theory Comput. (2002) 170–178Google Scholar
• Schrage L. A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. (1968) 16:687–690Link, Google Scholar
• Sleator D., Tarjan R. E. Amortized efficiency of list update and paging rules. Comm. ACM (1985) 28:202–208Crossref, Google Scholar
• Spielman D., Teng S. H. Smoothed analysis of termination of linear programming algorithms. Math. Programming (2003) 97(1–2):375–404Google Scholar
• Spielman D. A., Teng S. H. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM (2004) 51(3):385–463Crossref, Google Scholar
• Tanenbaum A. S.Modern Operating Systems (1992) (Prentice-Hall Inc., Upper Saddle River, NJ) Google Scholar