1 Search Results for "T'Kindt, Vincent"


Document
Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem

Authors: Lei Shang, Michele Garraffa, Federico Della Croce, and Vincent T'Kindt

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)


Abstract
This paper proposes an exact exponential algorithm for the problem of minimizing the total tardiness of jobs on a single machine. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity is O*(2.247^n) keeping the space complexity polynomial. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties.

Cite as

Lei Shang, Michele Garraffa, Federico Della Croce, and Vincent T'Kindt. Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{shang_et_al:LIPIcs.IPEC.2017.28,
  author =	{Shang, Lei and Garraffa, Michele and Della Croce, Federico and T'Kindt, Vincent},
  title =	{{Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.28},
  URN =		{urn:nbn:de:0030-drops-85468},
  doi =		{10.4230/LIPIcs.IPEC.2017.28},
  annote =	{Keywords: Exact exponential algorithm, Single machine total tardiness, Branch-and-merge}
}
  • Refine by Author
  • 1 Della Croce, Federico
  • 1 Garraffa, Michele
  • 1 Shang, Lei
  • 1 T'Kindt, Vincent

  • Refine by Classification

  • Refine by Keyword
  • 1 Branch-and-merge
  • 1 Exact exponential algorithm
  • 1 Single machine total tardiness

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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