@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",

}