“Nearly all” instances of an NP-hard scheduling problem appear to be easily solvable. Is that a unique case in scheduling? Доклады на конференциях
| Язык | Английский | ||
|---|---|---|---|
| Тип доклада | Пленарный | ||
| Url доклада | http://uiip.bas-net.by/event/tan-2021/programma.php | ||
| Конференция |
Танаевские чтения 2021 30-30 мар. 2021 , on-line |
||
| Авторы |
|
||
| Организации |
|
Реферат:
In this paper, we present an example of an NP-hard scheduling problem, “nearly all” instances of which appear to be easily solvable. The computational complexity of each problem instance is characterized very adequately by a non-standard problem parameter, equal to the ratio of two standard lower bounds on the optimum (for a given instance I).
Библиографическая ссылка:
Sevastyanov S.V.
“Nearly all” instances of an NP-hard scheduling problem appear to be easily solvable. Is that a unique case in scheduling?
Танаевские чтения 2021 30-30 Mar 2021
“Nearly all” instances of an NP-hard scheduling problem appear to be easily solvable. Is that a unique case in scheduling?
Танаевские чтения 2021 30-30 Mar 2021