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

DOI10.4230/LIPICS.IPEC.2020.25MaRDI QIDQ6089672FDOQ6089672

Authors: Jesper Nederlof, Céline M. F. Swennenhuis 

Publication date: 13 November 2023

Recommendations

• On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
• Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
• Scheduling and fixed-parameter tractability
• Scheduling and fixed-parameter tractability
• On the parametric complexity of schedules to minimize tardy tasks.

zbMATH Keywords

schedulingfixed-parameter tractabilityprecedence constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• The design of approximation algorithms
• Title not available (Why is that?)
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Can you beat treewidth?
• Color-coding
• Parameterized algorithms
• Scheduling with Outliers
• Scheduling
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Fourier meets M\"{o}bius: fast subset convolution
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Parameterized complexity of a coupled-task scheduling problem
• \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
• Scheduling partially ordered jobs faster than \(2^n\)
• Scheduling and fixed-parameter tractability
• Parameterized complexity of machine scheduling: 15 open problems
• On the parametric complexity of schedules to minimize tardy tasks.
• Open Problems in Throughput Scheduling
• Precedence scheduling with unit execution time is equivalent to parametrized biclique
• A note on combined job selection and sequencing problems

Cited In (3)

• On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
• Title not available (Why is that?)
• Moderate exponential-time algorithms for scheduling problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089672)