2026-07-21T14:12:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8233 2024-03-06T10:41:47Z ddc:004 open_access

An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint Calinescu, Gruia Jaehn, Florian Li, Minming Wang, Kai FPTAS Scheduling Approximation Algorithm In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be scheduled at a specified position. We give dynamic programs with pseudo-polynomial running time, and a fully polynomial-time approximation scheme (FPTAS). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gruia Calinescu and Florian Jaehn and Minming Li and Kai Wang 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.19 urn:nbn:de:0030-drops-82335 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.19 eng https://creativecommons.org/licenses/by/3.0/legalcode