An improved lower bound for rank four scheduling
From MaRDI portal
Publication:1785250
DOI10.1016/j.orl.2014.06.003zbMath1408.90123MaRDI QIDQ1785250
Lin Chen, Deshi Ye, Guo-Chuan Zhang
Publication date: 28 September 2018
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2014.06.003
90C60: Abstract computational complexity for mathematical programming problems
90B35: Deterministic scheduling theory in operations research
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
A PTAS for Scheduling Unrelated Machines of Few Different Types, An EPTAS for scheduling on unrelated machines of few different types, On the optimality of exact and approximation algorithms for scheduling problems
Cites Work
- Unnamed Item
- Approximation algorithms for scheduling unrelated parallel machines
- A simplified NP-complete satisfiability problem
- An optimal rounding gives a better approximation for scheduling unrelated machines
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- On the optimality of approximation schemes for the classical scheduling problem
- Minimum Makespan Scheduling with Low Rank Processing Times