An improved lower bound for rank four scheduling

DOI10.1016/j.orl.2014.06.003zbMath1408.90123OpenAlexW2016342875MaRDI 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

zbMATH Keywords

complexityschedulingAPX-hardness

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

On the optimality of exact and approximation algorithms for scheduling problems ⋮ A PTAS for Scheduling Unrelated Machines of Few Different Types ⋮ An EPTAS for scheduling on unrelated machines of few different types

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

This page was built for publication: An improved lower bound for rank four scheduling