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

Alexander Ageev, Mikhail Ivanov

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings
РедакторыAlexander Kononov, Michael Khachay, Valery A. Kalyagin, Panos Pardalos
ИздательSpringer Gabler
Страницы265-273
Число страниц9
ISBN (печатное издание)9783030499877
DOI
СостояниеОпубликовано - 1 янв 2020
Опубликовано для внешнего пользованияДа
Событие19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020 - Novosibirsk, Российская Федерация
Продолжительность: 6 июл 202010 июл 2020

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12095 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020
СтранаРоссийская Федерация
ГородNovosibirsk
Период06.07.202010.07.2020

Fingerprint Подробные сведения о темах исследования «An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать