Approximating Some Network Design Problems with Node Costs

DOI10.1007/978-3-642-03685-9_18MaRDI QIDQ3638881zbMATH OpenOpenAlexFDO

Authors Guy Kortsarz, Zeev Nutov

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.411.7298

zbMATH Keywords

approximation algorithmcovering treehardness of approximationmulticommodity buy at bulknetwork designnode costs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph
• Approximation algorithms for degree-constrained minimum-cost network-design problems

Cited in

(5)

• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• A Node Splitting Technique for Two Level Network Design Problems with Transition Nodes
• Minimum-cost network design with (dis)economies of scale
• Approximating Steiner Networks with Node Weights
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph

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 Q3638881)