An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays

Alexander Ageev; Mikhail Ivanov

doi:10.1007/978-3-030-49988-4_18

An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays

Alexander Ageev, Mikhail Ivanov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

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.

Original language	English
Title of host publication	Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings
Editors	Alexander Kononov, Michael Khachay, Valery A. Kalyagin, Panos Pardalos
Publisher	Springer Gabler
Pages	265-273
Number of pages	9
ISBN (Print)	9783030499877
DOIs	https://doi.org/10.1007/978-3-030-49988-4_18
Publication status	Published - 1 Jan 2020
Externally published	Yes
Event	19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 - Novosibirsk, Russian Federation Duration: 6 Jul 2020 → 10 Jul 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12095 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020
Country	Russian Federation
City	Novosibirsk
Period	06.07.2020 → 10.07.2020

Keywords

Approximation algorithm
Coupled-task scheduling
Inapproximability lower bound
Worst-case analysis

Access to Document

10.1007/978-3-030-49988-4_18

Link to publication in Scopus

Fingerprint Dive into the research topics of 'An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays'. Together they form a unique fingerprint.

Cite this

Ageev, A., & Ivanov, M. (2020). An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays. In A. Kononov, M. Khachay, V. A. Kalyagin, & P. Pardalos (Eds.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings (pp. 265-273). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12095 LNCS). Springer Gabler. https://doi.org/10.1007/978-3-030-49988-4_18

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

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

}

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_18

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

TY - GEN

T1 - An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays

AU - Ageev, Alexander

AU - Ivanov, Mikhail

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 -

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)). https://doi.org/10.1007/978-3-030-49988-4_18