Search Results

Documents authored by Jaehn, Florian


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

Authors: Gruia Calinescu, Florian Jaehn, Minming Li, and Kai Wang

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)


Abstract
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).

Cite as

Gruia Calinescu, Florian Jaehn, Minming Li, and Kai Wang. An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{calinescu_et_al:LIPIcs.ISAAC.2017.19,
  author =	{Calinescu, Gruia and Jaehn, Florian and Li, Minming and Wang, Kai},
  title =	{{An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.19},
  URN =		{urn:nbn:de:0030-drops-82335},
  doi =		{10.4230/LIPIcs.ISAAC.2017.19},
  annote =	{Keywords: FPTAS, Scheduling, Approximation Algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail