Approximating Some Network Design Problems with Node Costs

DOI10.1007/978-3-642-03685-9_18zbMath1255.68305OpenAlexW2087756717MaRDI QIDQ3638881

Zeev Nutov, Guy Kortsarz

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 algorithmnetwork designhardness of approximationcovering treemulticommodity buy at bulknode costs

Mathematics Subject Classification ID

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

Related Items (3)

Minimum-Cost Network Design with (Dis)economies of Scale ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ Approximating Steiner Networks with Node Weights

This page was built for publication: Approximating Some Network Design Problems with Node Costs