An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint

Autor:	Calinescu, G., Jaehn, F., Li, M., Wang, K.
Rok vydání:	2017
Předmět:	Computer Science - Data Structures and Algorithms F.2.2
Druh dokumentu:	Working Paper
Popis:	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). Comment: 13 pages, The 28th International Symposium on Algorithms and Computation (ISAAC)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1710.10904 Zobrazit plný text záznamu View this record from Arxiv