An improved approximation algorithm for scheduling under arborescence precedence constraints
From MaRDI portal
Publication:5089259
DOI10.4230/LIPIcs.MFCS.2020.84OpenAlexW3082001139MaRDI QIDQ5089259
Publication date: 18 July 2022
Full work available at URL: https://hal.science/hal-02943776
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
- Scheduling on unrelated machines under tree-like precedence constraints
- Makespan minimization in job shops
- Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling
- Non-Approximability Results for Scheduling Problems with Minsum Criteria
- Hardness of Precedence Constrained Scheduling on Identical Machines
- Towards Tight Lower Bounds for Scheduling Problems
- Complexity of Scheduling under Precedence Constraints
- 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
- Improved Approximation Algorithms for Shop Scheduling Problems
- Quasi-PTAS for scheduling with precedences using LP hierarchies
- Optimal Long Code Test with One Free Bit
- Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
This page was built for publication: An improved approximation algorithm for scheduling under arborescence precedence constraints