An improved approximation algorithm for scheduling under arborescence precedence constraints

DOI10.4230/LIPIcs.MFCS.2020.84OpenAlexW3082001139MaRDI QIDQ5089259

Nguyen Kim Thang

Publication date: 18 July 2022

Full work available at URL: https://hal.science/hal-02943776

zbMATH Keywords

schedulingprecedence constraintsLagrangian duality

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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