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

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2017.22

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

(18)

• (In-)approximability results for interval, resource restricted, and low rank scheduling
• Fairness in repetitive scheduling
• Complexity of scheduling few types of jobs on related and unrelated machines
• Scheduling two types of jobs with minimum makespan
• Scheduling meets n-fold integer programming
• Parameterized complexity of machine scheduling: 15 open problems
• An improved lower bound for rank four scheduling
• Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
• Minimum makespan scheduling with low rank processing times
• Tight lower bounds for block-structured integer programs
• Tight lower bounds for block-structured integer programs
• Improved approximation algorithms for two-stage flowshops scheduling problem
• Parameterized algorithms for block-structured integer programs with large entries
• (Near)-optimal algorithms for sparse separable convex integer programs
• On the optimality of exact and approximation algorithms for scheduling problems
• Faster Algorithms for Integer Programs with Block Structure
• Empowering the configuration-IP: new PTAS results for scheduling with setup times
• scientific article; zbMATH DE number 7559087 (Why is no real title available?)

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)