A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
type: Item
instance of: scholarly article
title: A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
zbMATH Open document ID: 1376.90028
author: René van Bevern
author: Ondřej Suchý
author: Rolf Niedermeier
published in: Journal of Scheduling
publication date: 2017-09-01T00:00:00Z
full work available at URL: https://arxiv.org/abs/1508.01657
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6767798
zbMATH Keywords: release times and deadlines
zbMATH Keywords: machine minimization
zbMATH Keywords: sequencing within intervals
zbMATH Keywords: shiftable intervals
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: NP-hard problem
MaRDI profile type: Publication
OpenAlex ID: W3102245374
arXiv ID: 1508.01657
cites work: Towards optimal and expressive kernelization for \(d\)-hitting set
cites work: Approximability and parameterized complexity of multicover by \(c\)-intervals
cites work: Interval scheduling and colorful independent sets
cites work: \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
cites work: An ℴ(log m)-Competitive Algorithm for Online Machine Minimization
cites work: Q4673408
cites work: Parameterized Algorithms
cites work: Fundamentals of parameterized complexity
cites work: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
cites work: On the parametric complexity of schedules to minimize tardy tasks.
cites work: Parametrized complexity theory.
cites work: Q4198056
cites work: Strip Graphs: Recognition and Scheduling
cites work: Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs
cites work: Bin packing with fixed number of bins revisited
cites work: Interval scheduling: A survey
cites work: A complete 4-parametric complexity classification of short shop scheduling problems
cites work: Shiftable intervals
cites work: Scheduling and fixed-parameter tractability
cites work: Reflections on Multivariate Algorithmics and Problem Parameterization
cites work: Q5710169
cites work: Q2963933
cites work: An introduction to multi-parameter complexity analysis of discrete problems
DOI: 10.1007/S10951-016-0478-9
description: scientific article