Approximating some network design problems with node costs

DOI10.1016/J.TCS.2011.04.013MaRDI QIDQ638508zbMATH OpenOpenAlexFDO

Authors Guy Kortsarz, Zeev Nutov

Publication date 12 September 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.04.013

zbMATH Keywords

computational complexitynetwork flowsapproximation algorithmsintegrality gapSteiner trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Flows in graphs (05C21)

Recommendations

• Approximation Algorithms for Network Design with Metric Costs
• scientific article; zbMATH DE number 1003253
• Approximation via cost sharing
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Approximation algorithms for a capacitated network design problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A threshold of ln n for approximating set cover
• An algorithm for the min concave cost flow problem
• Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
• Approximating Steiner Networks with Node Weights
• Approximating the single-sink link-installation problem in network design
• Approximation Schemes for the Restricted Shortest Path Problem
• Approximation algorithms for access network design
• Approximation algorithms for constrained node weighted Steiner tree problems
• Approximation algorithms for node-weighted buy-at-bulk network design
• Efficient recovery from power outage (extended abstract)
• Fixed-cost transportation problems
• Improved approximating algorithms for directed Steiner forest
• Many birds with one stone
• Minimum Concave Cost Flows in Certain Networks
• Networks synthesis and optimum network design problems: Models, solution methods and applications
• On non-uniform multicommodity buy-at-bulk network design
• The One-Terminal TELPAK Problem

Cited in

(1)

• A Node Splitting Technique for Two Level Network Design Problems with Transition Nodes

This page was built for publication: Approximating some network design problems with node costs

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