@inproceedings{ccf4622bdf3942c280106e61aa01efa2,
title = "An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays",
abstract = "We study the coupled-task single machine scheduling problem with equal exact delays and makespan as the objective function. It is known that the problem cannot be approximated with a factor better than 1.25 unless P$$=$$ NP. In this paper, we present a 2.5-approximation algorithm for this problem, which improves the best previously known approximation bound of 3. The algorithm runs in time$$O(n\log n)$$ where n is the number of jobs.",
keywords = "Approximation algorithm, Coupled-task scheduling, Inapproximability lower bound, Worst-case analysis",
author = "Alexander Ageev and Mikhail Ivanov",
year = "2020",
month = jan,
day = "1",
doi = "10.1007/978-3-030-49988-4_18",
language = "English",
isbn = "9783030499877",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Gabler",
pages = "265--273",
editor = "Alexander Kononov and Michael Khachay and Kalyagin, {Valery A.} and Panos Pardalos",
booktitle = "Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings",
address = "Germany",
note = "19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 ; Conference date: 06-07-2020 Through 10-07-2020",
}