On the optimality of approximation schemes for the classical scheduling problem

DOI10.1137/1.9781611973402.50zbMath1421.68201arXiv1310.0398OpenAlexW1540235234MaRDI QIDQ5384011

Lin Chen, Guo-Chuan Zhang, Klaus Jansen

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.0398

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)

Related Items (9)

On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Scheduling with machine conflicts ⋮ Vector scheduling with rejection on a single machine ⋮ The piggyback transportation problem: transporting drones launched from a flying warehouse ⋮ An improved lower bound for rank four scheduling ⋮ Bounding the Running Time of Algorithms for Scheduling and Packing Problems ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ Closing the Gap for Pseudo-Polynomial Strip Packing ⋮ Closing the Gap for Makespan Scheduling via Sparsification Techniques

This page was built for publication: On the optimality of approximation schemes for the classical scheduling problem