An improved approximation algorithm for scheduling under arborescence precedence constraints
From MaRDI portal
Publication:5089259
DOI10.4230/LIPICS.MFCS.2020.84OpenAlexW3082001139MaRDI QIDQ5089259FDOQ5089259
Authors: Nguyen Kim Thang 
Publication date: 18 July 2022
Full work available at URL: https://hal.science/hal-02943776
Cites Work
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Complexity of Scheduling under Precedence Constraints
- Title not available (Why is that?)
- Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
- Towards tight lower bounds for scheduling problems
- Title not available (Why is that?)
- Makespan minimization in job shops: a polynomial time approximation scheme
- Improved Approximation Algorithms for Shop Scheduling Problems
- Scheduling on unrelated machines under tree-like precedence constraints
- Optimal Long Code Test with One Free Bit
- Non-approximability results for scheduling problems with minsum criteria
- Hardness of precedence constrained scheduling on identical machines
- Resource augmentation for weighted flow-time explained by dual fitting
- Lagrangian duality in online scheduling with resource augmentation and speed scaling
- A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
- Quasi-PTAS for scheduling with precedences using LP hierarchies
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- Lift and project algorithms for precedence constrained scheduling to minimize completion time
Cited In (1)
This page was built for publication: An improved approximation algorithm for scheduling under arborescence precedence constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089259)
