On the fine-grained parameterized complexity of partial scheduling to minimize the makespan

DOI10.1007/s00453-022-00970-8OpenAlexW3114276557MaRDI QIDQ2161009

Jesper Nederlof, Céline M. F. Swennenhuis

Publication date: 3 August 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.03185

zbMATH Keywords

schedulingprecedence constraintsfixed-parameter tractability

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey on offline scheduling with rejection
• Scheduling partially ordered jobs faster than \(2^n\)
• Interval scheduling and colorful independent sets
• Scheduling and fixed-parameter tractability
• Parameterized complexity of machine scheduling: 15 open problems
• On the parametric complexity of schedules to minimize tardy tasks.
• \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
• Parameterized complexity of a coupled-task scheduling problem
• Precedence Scheduling with Unit Execution Time is Equivalent to Parametrized Biclique
• Open Problems in Throughput Scheduling
• The Design of Approximation Algorithms
• Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
• Fourier meets M\"{o}bius: fast subset convolution
• Scheduling with Outliers
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Color-coding
• A note on combined job selection and sequencing problems
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Parameterized Algorithms
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Bounding the Running Time of Algorithms for Scheduling and Packing Problems
• Scheduling

This page was built for publication: On the fine-grained parameterized complexity of partial scheduling to minimize the makespan