TY - GEN
T1 - On the Fine-Grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan
AU - Nederlof, Jesper
AU - Swennenhuis, Céline M. F.
PY - 2020
Y1 - 2020
N2 - We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f(k)n^풪(1) or n^풪(f(k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in 햯, NP-complete and fixed-parameter tractable by k, or 햶[1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an 풪(8^k k(|V|+|E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V,E) is the graph with precedence constraints.
AB - We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f(k)n^풪(1) or n^풪(f(k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in 햯, NP-complete and fixed-parameter tractable by k, or 햶[1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an 풪(8^k k(|V|+|E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V,E) is the graph with precedence constraints.
KW - Fixed-Parameter Tractability
KW - Scheduling
KW - Precedence Constraints
U2 - 10.4230/LIPIcs.IPEC.2020.25
DO - 10.4230/LIPIcs.IPEC.2020.25
M3 - Conference contribution
SN - 978-3-95977-172-6
T3 - Leibniz International Proceedings in Informatics (LIPIcs)
SP - 25:1-25:17
BT - 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
A2 - Cao, Yixin
A2 - Pilipczuk, Marcin
PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
ER -