# An Optimal Incremental Algorithm for Minimizing Lateness with Rejection

Title | An Optimal Incremental Algorithm for Minimizing Lateness with Rejection |

Publication Type | Journal Articles |

Year of Publication | 2008 |

Authors | Khuller S, Mestre J |

Journal | Algorithms-ESA 2008 |

Pagination | 601 - 610 |

Date Published | 2008/// |

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 |