Conditional hardness of precedence constrained scheduling on identical machines
From MaRDI portal
Publication:2875202
DOI10.1145/1806689.1806791zbMath1293.68070OpenAlexW1978018278MaRDI QIDQ2875202
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806791
Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (6)
Approximation Algorithms for Scheduling with Resource and Precedence Constraints ⋮ Bi-Covering: Covering Edges with Two Small Subsets of Vertices ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ Quasi-PTAS for scheduling with precedences using LP hierarchies ⋮ Makespan minimization with OR-precedence constraints ⋮ A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
This page was built for publication: Conditional hardness of precedence constrained scheduling on identical machines
