Approximating buy-at-bulk and shallow-light k-Steiner trees
From MaRDI portal
Publication:1017907
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
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)