Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2014.04.004 | Theoretical Computer Science |
Keywords | DocType | Volume |
Reoptimization,Machine scheduling,Min-sum cost function | Journal | 540 |
ISSN | Citations | PageRank |
0304-3975 | 5 | 0.43 |
References | Authors | |
18 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Boria | 1 | 59 | 7.23 |
| Federico Della Croce | 2 | 399 | 41.60 |