Parameterized and approximation results for scheduling with a low rank processing time matrix

DOI10.4230/LIPICS.STACS.2017.22MaRDI QIDQ4636620zbMATH OpenFDO

Authors Lin Chen, Dániel Marx, Deshi Ye, Guochuan Zhang

Publication date 19 April 2018

zbMATH Keywords

schedulingAPX-hardnessexponential time hypothesisparameterized algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Minimum makespan scheduling with low rank processing times
• An improved lower bound for rank four scheduling
• Fixed-parameter approximation schemes for weighted flowtime
• On the optimality of approximation schemes for the classical scheduling problem
• Scheduling meets \(n\)-fold integer programming

Cited in

(10)

• Scheduling meets \(n\)-fold integer programming
• Minimum makespan scheduling with low rank processing times
• On the optimality of exact and approximation algorithms for scheduling problems
• Empowering the configuration-IP: new PTAS results for scheduling with setup times
• Parameterized complexity of machine scheduling: 15 open problems
• An improved lower bound for rank four scheduling
• Faster Algorithms for Integer Programs with Block Structure
• scientific article; zbMATH DE number 7559087 (Why is no real title available?)
• Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
• Improved approximation algorithms for two-stage flowshops scheduling problem

This page was built for publication: Parameterized and approximation results for scheduling with a low rank processing time matrix

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