“Nearly all” instances of an NP-hard scheduling problem appear to be easily solvable. Is that a unique case in scheduling? Conference attendances
| Language | Английский | ||
|---|---|---|---|
| Participant type | Пленарный | ||
| URL | http://uiip.bas-net.by/event/tan-2021/programma.php | ||
| Conference |
Танаевские чтения 2021 30-30 Mar 2021 , on-line |
||
| Authors |
|
||
| Affiliations |
|
Abstract:
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).
Cite:
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