%0 Journal Article
%J Algorithms-ESA 2008
%D 2008
%T An Optimal Incremental Algorithm for Minimizing Lateness with Rejection
%A Khuller, Samir
%A Mestre,J.
%X 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.
%B Algorithms-ESA 2008
%P 601 - 610
%8 2008///
%G eng
%R 10.1007/978-3-540-87744-8_50