Standard
An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays. / Ageev, Alexander; Ivanov, Mikhail.
Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. ed. / Alexander Kononov; Michael Khachay; Valery A. Kalyagin; Panos Pardalos. Springer Gabler, 2020. p. 265-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12095 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Ageev, A & Ivanov, M 2020,
An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays. in A Kononov, M Khachay, VA Kalyagin & P Pardalos (eds),
Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12095 LNCS, Springer Gabler, pp. 265-273, 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020, Novosibirsk, Russian Federation,
06.07.2020.
https://doi.org/10.1007/978-3-030-49988-4_18APA
Vancouver
Ageev A, Ivanov M.
An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays. In Kononov A, Khachay M, Kalyagin VA, Pardalos P, editors, Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. Springer Gabler. 2020. p. 265-273. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-49988-4_18
Author
Ageev, Alexander ; Ivanov, Mikhail. /
An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays. Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. editor / Alexander Kononov ; Michael Khachay ; Valery A. Kalyagin ; Panos Pardalos. Springer Gabler, 2020. pp. 265-273 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@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",
note = "The work was supported by the program of fundamental scientific researches of the SB RAS, project N 0314-2019-0014; 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 ; Conference date: 06-07-2020 Through 10-07-2020",
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",
}
RIS
TY - GEN
T1 - An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays
AU - Ageev, Alexander
AU - Ivanov, Mikhail
N1 - The work was supported by the program of fundamental scientific researches of the SB RAS, project N 0314-2019-0014
PY - 2020/1/1
Y1 - 2020/1/1
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - Coupled-task scheduling
KW - Inapproximability lower bound
KW - Worst-case analysis
UR - http://www.scopus.com/inward/record.url?scp=85087776481&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-49988-4_18
DO - 10.1007/978-3-030-49988-4_18
M3 - Conference contribution
AN - SCOPUS:85087776481
SN - 9783030499877
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 265
EP - 273
BT - Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings
A2 - Kononov, Alexander
A2 - Khachay, Michael
A2 - Kalyagin, Valery A.
A2 - Pardalos, Panos
PB - Springer Gabler
T2 - 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020
Y2 - 6 July 2020 through 10 July 2020
ER -
