Approximating some network design problems with node costs

DOI10.1016/j.tcs.2011.04.013zbMath1236.68297OpenAlexW3023424394MaRDI QIDQ638508

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 algorithmsSteiner treesintegrality gap

Mathematics Subject Classification ID

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

Cites Work

• Approximation algorithms for access network design
• An algorithm for the min concave cost flow problem
• Approximating the Single-Sink Link-Installation Problem in Network Design
• Efficient recovery from power outage (extended abstract)
• A threshold of ln n for approximating set cover
• Fixed-cost transportation problems
• On non-uniform multicommodity buy-at-bulk network design
• Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
• Networks synthesis and optimum network design problems: Models, solution methods and applications
• Approximation Schemes for the Restricted Shortest Path Problem
• Bicriteria Network Design Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Approximation algorithms for constrained for constrained node weighted steiner tree problems
• Many birds with one stone
• Approximating Steiner Networks with Node Weights
• Minimum Concave Cost Flows in Certain Networks
• The One-Terminal TELPAK Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item