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

DOI10.4230/LIPICS.STACS.2017.22zbMATH Open1402.68085MaRDI QIDQ4636620FDOQ4636620

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

Publication date: 19 April 2018

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

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)

Cited In (12)

• An EPTAS for scheduling on unrelated machines of few different types
• 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
• Improved approximation algorithms for two-stage flowshops scheduling problem
• Structural parameters for scheduling with assignment restrictions
• 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
• Title not available (Why is that?)

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)