Approximating buy-at-bulk and shallow-light k-Steiner trees

DOI10.1007/S00453-007-9013-XzbMATH Open1176.68242OpenAlexW2098907131MaRDI QIDQ1017907FDOQ1017907

Authors: Mohammad T. Hajiaghayi, Guy Kortsarz, Mohammad 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

Recommendations

• 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
• Approximating Some Network Design Problems with Node Costs
• Approximation algorithms for nonuniform buy-at-bulk network design

zbMATH Keywords

cost functionsnetwork design problems

Mathematics Subject Classification ID

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

Cites Work

• Approximation algorithms for combinatorial problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Bicriteria Network Design Problems
• Generalized submodular cover problems and applications
• Title not available (Why is that?)
• A tight bound on approximating arbitrary metrics by tree metrics
• The dense \(k\)-subgraph problem
• Simpler and better approximation algorithms for network design
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Cost-Distance: Two Metric Network Design
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Title not available (Why is that?)
• A constant factor approximation for the single sink edge installation problems
• A deterministic algorithm for the cost-distance problem
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Approximating the single-sink link-installation problem in network design
• On non-uniform multicommodity buy-at-bulk network design
• Approximation algorithms for access network design
• On the approximability of some network design problems
• Title not available (Why is that?)

Cited In (11)

• Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
• Steiner shallow-light trees are exponentially lighter than spanning ones
• Cost-Distance: Two Metric Network Design
• Brief announcement: Characterizing demand graphs for (fixed-parameter) shallow-light Steiner network
• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• One tree suffices: a simultaneous \(O(1)\)-approximation for single-sink buy-at-bulk
• Network design problems with bounded distances via shallow-light Steiner trees
• Approximating Some Network Design Problems with Node Costs
• Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph
• 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

This page was built for publication: Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017907)