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

DOI10.1007/S00453-007-9013-XMaRDI QIDQ1017907zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(11)

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

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)