@article {15256,
title = {An Optimal Incremental Algorithm for Minimizing Lateness with Rejection},
journal = {Algorithms-ESA 2008},
year = {2008},
month = {2008///},
pages = {601 - 610},
abstract = {This paper re-examines the classical problem of minimizing maximum lateness which is defined as follows: given a collection of n jobs with processing times and due dates, in what order should they be processed on a single machine to minimize maximum lateness? The lateness of a job is defined as its completion time minus its due date. This problem can be solved easily by ordering the jobs in non-decreasing due date order. We now consider the following question: which subset of k jobs should we reject to reduce the maximum lateness by the largest amount? While this problem can be solved optimally in polynomial time, we show the following surprising result: there is a fixed permutation of the jobs, such that for all k, if we reject the first k jobs from this permutation, we derive an optimal solution for the problem in which we are allowed to reject k jobs. This allows for an incremental solution in which we can keep incrementally rejecting jobs if we need a solution with lower maximum lateness value. Moreover, we also develop an optimal O(n logn) time algorithm to find this permutation.},
doi = {10.1007/978-3-540-87744-8_50},
author = {Khuller, Samir and Mestre,J.}
}