A 2-approximation algorithm for the network substitution problem

DOI10.1016/j.orl.2005.03.005zbMath1080.90080OpenAlexW1993809775MaRDI QIDQ2583715

Nicolai Pisaruk

Publication date: 18 January 2006

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2005.03.005

zbMATH Keywords

networkcomplexityschedulingapproximation algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Randomized algorithms (68W20)

Cites Work

• The boundaries of submodular functions
• A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms

This page was built for publication: A 2-approximation algorithm for the network substitution problem