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 proceedingConference contributionResearchpeer-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 languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings
EditorsAlexander Kononov, Michael Khachay, Valery A. Kalyagin, Panos Pardalos
PublisherSpringer Gabler
Pages265-273
Number of pages9
ISBN (Print)9783030499877
DOIs
Publication statusPublished - 1 Jan 2020
Externally publishedYes
Event19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 - Novosibirsk, Russian Federation
Duration: 6 Jul 202010 Jul 2020

Publication series

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

Conference

Conference19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020
CountryRussian Federation
CityNovosibirsk
Period06.07.202010.07.2020

Keywords

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

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