Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
In this note, we give a 1.47-approximation algorithm for the preemptive scheduling of jobs with release dates on a single machine so as to minimize the weighted sum of job completion times; this problem is denoted by 1|rj, pmtn|∑jwjCj in the notation of Lawler et al. Our result improves on a 2-approximation algorithm due to Hall et al. Math. Oper. Res. 22 (1997) 513-544, and also yields an improved bound on the quality of a well-known linear programming relaxation of the problem.
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Peter Wendt
Electronic Imaging: Advanced Devices and Systems 1990
F. Odeh, I. Tadjbakhsh
Archive for Rational Mechanics and Analysis
Minghong Fang, Zifan Zhang, et al.
CCS 2024