On the Fine-grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan

Area of Science:

• Computer Science
• Operations Research
• Algorithm Design

Background:

• Scheduling problems involve optimizing job processing on machines.
• Partial scheduling considers optimizing a subset (k) of jobs.
• Parameterized complexity analyzes algorithm runtime based on input parameters.

Purpose of the Study:

• To determine the fine-grained parameterized complexity of partial scheduling problems.
• To analyze variants minimizing makespan across different machine types and constraints.
• To investigate the existence of efficient algorithms with runtimes dependent on parameter k.

Main Methods:

• Categorization of scheduling problem variants based on parameterized complexity classes (FPT, W[1]-complete, NP-hard).
• Development of algorithms with runtimes of the form f(k) * poly(n).
• Analysis of runtime optimality using the Exponential Time Hypothesis.

Main Results:

• Classification of all partial scheduling variants into complexity classes.
• Identification of fixed-parameter tractable (FPT) variants solvable efficiently for small k.
• Development of an O(2^k * n) time algorithm for partial scheduling with unit jobs, precedence, and release dates.

Conclusions:

• Partial scheduling problems exhibit diverse parameterized complexities.
• Efficient algorithms exist for certain variants, particularly when parameterized by k.
• The study provides a comprehensive complexity landscape and near-optimal algorithms for makespan minimization.