2026-08-16T03:23:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24151 2025-11-12T13:33:42Z ddc:004 open_access

An EPTAS for Minimizing the Total Weighted Completion Time of Jobs with Release Dates on Uniformly Related Machines Epstein, Leah Levin, Asaf Scheduling algorithms Approximation schemes Min-sum objectives Scheduling of independent jobs with release dates so as to minimize the total weighted completion time is a well-known scheduling problem. Here, we study it for the classic machine environment of uniformly related machines. An efficient polynomial time approximation scheme (an EPTAS) is a family of (1+ε)-approximation algorithms where the running time is bounded by a polynomial in the input size times a function of ε > 0. For problems that are NP-hard in the strong sense, as it is the case for the problem studied here, an EPTAS is the best possible approximation scheme. We design an EPTAS for the problem by employing known techniques and introducing a large collection of new methods. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leah Epstein and Asaf Levin 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.44 urn:nbn:de:0030-drops-241515 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.44 eng https://creativecommons.org/licenses/by/4.0/legalcode