Smoothed performance guarantees for local search

Angel, E.: A survey of approximation results for local search algorithms. In: Bampis, E., Jansen, K., Kenyon, C. (eds.) Efficient Approximation and Online Algorithms, Volume 3484 of LNCS, pp. 30–73. Springer, Heidelberg (2006)

Aspnes, J., Azar, Y., Fiat, A., Plotkin, S.A., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3), 486–504 (1997)

Awerbuch, B., Azar, Y., Richter, Y., Tsur, D.: Tradeoffs in worst-case equilibria. Theor. Comput. Sci. 361, 200–209 (2006)

Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Schäfer, G., Vredeveld, T.: Average case and smoothed competitive analysis for the multi-level feedback algorithm. Math. Oper. Res. 31(3), 85–108 (2006)

Beier, R., Vöcking, B.: Random knapsack in expected polynomial time. J. Comput. Syst. Sci. 69(3), 306–329 (2004)

Cho, Y., Sahni, S.: Bounds for list schedules on uniform processors. SIAM J. Comput. 9, 91–103 (1980)

Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. ACM Trans. Algorithms 3(1) article 4 (2007)

Englert, M., Röglin, H., Vöcking, B.: Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1295–13004 (2007)

Finn, G., Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. BIT 19, 312–320 (1979)

Garey, M.R., Johnson, D.S.: Computers and Intractibility: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)

Glass, C.A., Kellerer, H.: Parallel machine scheduling with job assignment restrictions. Naval Res. Logist. 54(3), 250–257 (2007)

Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966)

Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287–326 (1979)

Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for machine scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17, 539–551 (1988)

Hoefer, M., Souza, A.: Tradeoffs and average-case equilibria in selfish routing. ACM Trans. Comput. Theory 2(1) article 2 (2010)

Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13–30 (1963)

Leung, J.Y.T., Li, C.L.: Scheduling with processing set restrictions: a survey. Int. J. Prod. Econ. 116, 251–262 (2008)

Li, C.L.: Scheduling unit-length jobs with machine eligibility restrictions. Eur. J. Oper. Res. 174, 1325–1328 (2006)

Michiels, W.P.A.J., Aarts, E.H.L., Korst, J.H.M.: Theoretical Aspects of Local Search. Springer, Heidelberg (2007)

Ou, J., Leung, J.Y.-T., Li, C.L.: Scheduling parallel machines with inclusive set restrictions. Naval Res. Logist. 55(4), 328–338 (2008)

Rutten, C., Recalde, D., Schuurman, P., Vredeveld, T.: Performance guarantees of jump neighborhoods on restricted related parallel machines. Oper. Res. Lett. 40, 287–291 (2012)

Schäfer, G., Sivadasan, N.: Topology matters: smoothed competitiveness of metrical task systems. Theor. Comput. Sci. 341(1–3), 3–14 (2005)

Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. Inf. J. Comput. 19(1), 52–63 (2007)

Spielman, D.A., Teng, S.H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385–463 (2004)

Spielman, D.A., Teng, S.H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76–84 (2009)

Vöcking, B.: Selfish load balancing. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, chapter 20. Cambridge University Press, New York (2007)