25579

Автор(ы): 

Гафаров Е. Р. (ИПУ РАН, Лаборатория 68)
Лазарев А. А. (ИПУ РАН, Лаборатория 68)

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

A special case of the single-machine total tardiness problem is NP-hard

Электронная публикация: 

Да

ISBN/ISSN: 

1064-2307

Наименование источника: 

  • Journal of Computer and Systems Sciences International

Обозначение и номер тома: 

45, No.3.

Город: 

  • Москва

Издательство: 

  • Published in Russian in Izvestiya Akademii Nauk. Teoriya i Sistemy Upravleniya

Год издания: 

2006

Страницы: 

450-458
Аннотация
In this paper, it is shown that the special case B-1 of the single-machine total tardiness problem 1∥∑Tj is NP-hard in the ordinary sense. For this case, there exists a pseudo-polynomial algorithm with run time 𝒪 n . .

Библиографическая ссылка: 

Гафаров Е.Р., Лазарев А.А. A special case of the single-machine total tardiness problem is NP-hard / Journal of Computer and Systems Sciences International. М.: Published in Russian in Izvestiya Akademii Nauk. Teoriya i Sistemy Upravleniya, 2006. 45, No.3. С. 450-458.