“Toward the smoothed analysis of k-jump neighborhood”
In this talk, we consider the problem of scheduling jobs on identical parallel machines to minimize the makespan. We analyze a simple local search method w.r.t. the so-called k-jump neighborhood. We will talk about the worst-case running time of the algorithm. The idea of the research is to see whether the worst-case running time can be improved by applying smoothed analysis.