A 2-approximation algorithm for the network substitution problem

DOI10.1016/J.ORL.2005.03.005MaRDI QIDQ2583715zbMATH OpenOpenAlexFDO

Authors N. N. 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

approximation algorithmcomplexitynetworkscheduling

Mathematics Subject Classification ID

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

Recommendations

• Approximation Algorithms for Network Design Problems on Bounded Subsets
• Approximation Algorithms for a Network Design Problem
• Approximation algorithms for certain network improvement problems
• Approximation algorithms for network design problems
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem
• On the approximability of some network design problems
• On the approximability of some network design problems
• Two algorithms for the subset interconnection design problem
• scientific article; zbMATH DE number 1670539
• Approximation algorithms for a capacitated network design problem

Cites work

• A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
• 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
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• The boundaries of submodular functions

Cited in

(1)

• Network installation under convex costs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583715)