2019/12/06 by Jesper Nederlof, Nederlof, Jesper, Céline M. F. Swennenhuis +1
Computer Science · Engineering · #68Q25 #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1912.03185
openalex publication_date 2019/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)nO(1) or nO(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 P, NP-complete and fixed-parameter tractable by k, or W[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 O(8kk(|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.