.png){kind=icon}
.png){kind=icon}
Return
Moderate exponential-time algorithms for scheduling problems
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-024-06289-7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This survey investigates the field of moderate exponential-time algorithms for NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{N}\mathcal{P}}$$\end{document}-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.
Keywords:
Scheduling theory
Exact algorithms
Complexity
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W
View more organizations