Towards Tight Lower Bounds for Scheduling Problems
From MaRDI portal
Publication:3452775
DOI10.1007/978-3-662-48350-3_11zbMath1466.68040arXiv1507.01906OpenAlexW1495318531MaRDI QIDQ3452775
Abbas Bazzi, Ashkan Norouzi-Fard
Publication date: 19 November 2015
Published in: Algorithms - ESA 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.01906
Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Approximation Algorithms for Scheduling with Resource and Precedence Constraints ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ An improved approximation algorithm for scheduling under arborescence precedence constraints ⋮ Non-Clairvoyant Precedence Constrained Scheduling.
Cites Work
- Precedence constrained scheduling in \((2-\frac{7}{3p+1})\) optimal
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Scheduling with Deadlines and Loss Functions
- An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines
- The Design of Approximation Algorithms
- Hardness of Precedence Constrained Scheduling on Identical Machines
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- A New Algorithm for Preemptive Scheduling of Trees
- Computational Complexity of Discrete Optimization Problems
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
- Optimal Long Code Test with One Free Bit
- Bounds for Certain Multiprocessing Anomalies
- Optimal Preemptive Scheduling on Two-Processor Systems
- Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
This page was built for publication: Towards Tight Lower Bounds for Scheduling Problems
