This survey investigates the field of moderate exponential-time algorithms for NP-hard scheduling problems, i.e., exact algorithms whose worst-case time complexity is moderately exponential with respect to brute force algorithms. Scheduling problems are very challenging problems for which interesting results have emerged in the literature since 2010. We will provide a comprehensive overview of the known results of these problems before detailing three general techniques to derive moderate exponential-time algorithms. These techniques are Sort&Search, Inclusion-Exclusion and Branching. In the last part of this survey, we will focus on side topics such as approximation in moderate exponential time, the design of lower bounds on worst-case time complexities or fixed-parameter tractability. We will also discuss the potential benefits of moderate exponential-time algorithms for efficiently solving in practice scheduling problems.
Moderate exponential-time algorithms for scheduling problems / T'Kindt, V.; Della Croce, F.; Liedloff, M.. - In: 4OR. - ISSN 1619-4500. - 20:4(2022), pp. 533-566. [10.1007/s10288-022-00525-1]
Moderate exponential-time algorithms for scheduling problems
T'kindt V.;Della Croce F.;
2022
Abstract
This survey investigates the field of moderate exponential-time algorithms for NP-hard scheduling problems, i.e., exact algorithms whose worst-case time complexity is moderately exponential with respect to brute force algorithms. Scheduling problems are very challenging problems for which interesting results have emerged in the literature since 2010. We will provide a comprehensive overview of the known results of these problems before detailing three general techniques to derive moderate exponential-time algorithms. These techniques are Sort&Search, Inclusion-Exclusion and Branching. In the last part of this survey, we will focus on side topics such as approximation in moderate exponential time, the design of lower bounds on worst-case time complexities or fixed-parameter tractability. We will also discuss the potential benefits of moderate exponential-time algorithms for efficiently solving in practice scheduling problems.File | Dimensione | Formato | |
---|---|---|---|
s10288-022-00525-1.pdf
accesso riservato
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
732.59 kB
Formato
Adobe PDF
|
732.59 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2979583