Back to Search
Start Over
Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions.
- Source :
-
INFORMS Journal on Computing . May/Jun2024, Vol. 36 Issue 3, p836-848. 13p. - Publication Year :
- 2024
-
Abstract
- In this paper we consider the fundamental scheduling problem of minimizing the weighted number of tardy jobs on a single machine. We present a simple pseudo polynomial-time algorithm for this problem that improves upon the classical Lawler and Moore algorithm from the late 60's under certain scenarios and parameter settings. Our algorithm uses (max,+)-convolutions as its main tool, exploiting recent improved algorithms for computing such convolutions, and obtains several different running times depending on the specific improvement used. We also provide a related lower bound for the problem under a variant of the well-known Strong Exponential Time Hypothesis (SETH). History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by the Israel Science Foundation [Grant 1070/20]. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYNOMIAL time algorithms
*ONLINE algorithms
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 10919856
- Volume :
- 36
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- INFORMS Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 177990662
- Full Text :
- https://doi.org/10.1287/ijoc.2022.0307