A Pseudopolynomial Algorithm to Minimize Maximum Lateness on Multiple Related Machines

2020/01/22 by Du, Elbert, Zhang, Stan
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2001.07887

Abstract

In this paper, we will find a pseudopolynomial algorithm to solve Qm | | L_max and then we will prove that it is impossible to get any constant-factor approximation in polynomial time, and thus also impossible to have a PTAS for this problem. We will also show that the the problem when we don't assume a fixed number of machines, P | | L_max, is strongly NP-hard.

Related

• An Approximate Pareto Set for Minimizing the Maximum Lateness and Makespan on Parallel Machines
• Faster Minimization of Total Weighted Completion Time on Parallel Machines
• Minimum total weighted completion time: Faster approximation schemes
• Lower bounds for algebraic machines, semantically
• A note on the paper "Minimizing total tardiness on parallel machines with preemptions" by Kravchenko and Werner [2010]