Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees

DOI10.1007/s00453-007-9013-xzbMath1176.68242OpenAlexW2098907131MaRDI QIDQ1017907

Guy Kortsarz, Mohammad Taghi Hajiaghayi, Mohammad R. Salavatipour

Publication date: 13 May 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9013-x

zbMATH Keywords

cost functionsnetwork design problems

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Unnamed Item, Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph, Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics, Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones, On Hop-Constrained Steiner Trees in Tree-Like Metrics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for access network design
• Approximation algorithms for combinatorial problems
• Generalized submodular cover problems and applications
• Approximating the Single-Sink Link-Installation Problem in Network Design
• Cost-Distance: Two Metric Network Design
• Simpler and better approximation algorithms for network design
• On non-uniform multicommodity buy-at-bulk network design
• Saving an epsilon
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Approximation Schemes for the Restricted Shortest Path Problem
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Bicriteria Network Design Problems
• A constant factor approximation for the single sink edge installation problems
• A tight bound on approximating arbitrary metrics by tree metrics
• The dense \(k\)-subgraph problem