Cover Image

Minimizing the Number of Tardy Jobs and Maximal Tardiness on a Single Machine is NP-hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Heeger, Klaus, Hermelin, Danny, Pinedo, Michael L., Shabtay, Dvir
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
by: Heeger, Klaus, et al.
Published: (2024)

Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
by: Heeger, Klaus, et al.
Published: (2024)

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
by: Kaul, Matthias, et al.
Published: (2024)

Faster Minimization of Total Weighted Completion Time on Parallel Machines
by: Hermelin, Danny, et al.
Published: (2025)

Fast Makespan Minimization via Short ILPs
by: Hermelin, Danny, et al.
Published: (2026)

Approximation Algorithms for Fair Repetitive Scheduling
by: Hermelin, Danny, et al.
Published: (2025)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Fair Repetitive Interval Scheduling
by: Heeger, Klaus, et al.
Published: (2024)

Fairness in Repetitive Scheduling
by: Hermelin, Danny, et al.
Published: (2021)

Lawler-Moore Speedups via Additive Combinatorics
by: Bringmann, Karl, et al.
Published: (2026)

Robust Permutation Flowshops Under Budgeted Uncertainty
by: Goldberg, Noam, et al.
Published: (2026)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
by: Stoian, Mihail
Published: (2024)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
by: Bampis, Evripidis, et al.
Published: (2025)

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
by: Bampis, Evripidis, et al.
Published: (2024)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
by: Murakami, Hitoshi, et al.
Published: (2024)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
by: Bartlmae, Simon, et al.
Published: (2024)

Online Flow Time Minimization with Gradually Revealed Jobs
by: Lindermayr, Alexander, et al.
Published: (2026)

The Buffer Minimization Problem for Scheduling Flow Jobs with Conflicts
by: Haas, Niklas, et al.
Published: (2025)

Minimizing the Weighted Makespan with Restarts on a Single Machine
by: Amouzandeh, Aflatoun, et al.
Published: (2025)

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions
by: Berg, Magnus
Published: (2024)

Scheduling on a Stochastic Number of Machines
by: Buchem, Moritz, et al.
Published: (2024)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling
by: Jansen, Klaus, et al.
Published: (2026)

Minimizing Cost Rather Than Maximizing Reward in Restless Multi-Armed Bandits
by: Witter, R. Teal, et al.
Published: (2024)

A Competitive Algorithm for Throughput Maximization on Identical Machines
by: Moseley, Benjamin, et al.
Published: (2021)

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

NP-Completeness for the Space-Optimality of Double-Array Tries
by: Bannai, Hideo, et al.
Published: (2024)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
by: Jansen, Klaus, et al.
Published: (2024)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
by: Rohwedder, Lars
Published: (2025)

DNA Probe Computing System for Solving NP-Complete Problems
by: Xu, Jin, et al.
Published: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
by: Dhar, Anubhav, et al.
Published: (2025)

Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
by: Chen, Tianqi, et al.
Published: (2025)

Algorithmic Reductions: Network Flow and NP-Completeness in Real-World Scheduling Problems
by: Sinhal, Anay, et al.
Published: (2026)

The APX-hardness of the Traveling Tournament Problem
by: Zhao, Jingyang, et al.
Published: (2023)

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
by: Amir, Amihood, et al.
Published: (2026)

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
by: Brinkop, Hauke, et al.
Published: (2025)

Searching 2D-Strings for Matching Frames
by: Boneh, Itai, et al.
Published: (2023)

Structural Results for High-Multiplicity Scheduling on Uniform Machines
by: Brinkop, Hauke, et al.
Published: (2022)

Minimizing the Minimizers via Alphabet Reordering
by: Verbeek, Hilde, et al.
Published: (2024)