Approximating some network design problems with node costs

DOI10.1016/J.TCS.2011.04.013zbMATH Open1236.68297OpenAlexW3023424394MaRDI QIDQ638508FDOQ638508

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

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

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)

Cites Work

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

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)