Reoptimization in machine scheduling

This paper studies reoptimization versions of various min-sum scheduling problems. The reoptimization setting can generally be described as follows: given an instance of the problem for which an optimal solution is provided and given some local perturbations on that instance, we search for a near-optimal solution for the modified instance requiring very little computation. We focus on two kinds of modifications: job-insertions and job-deletions. For all reoptimization problems considered, we show how very simple reoptimization algorithms can ensure constant approximation ratios, and also provide some lower bounds for whole classes of reoptimization algorithms.