Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph

DOI10.1007/s10878-014-9774-5zbMath1341.90113OpenAlexW2014708079MaRDI QIDQ5963643

Mohammad R. Salavatipour, M. Reza Khani

Publication date: 23 February 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-014-9774-5

zbMATH Keywords

combinatorial optimizationnetwork designapproximation algorithmsSteiner tree\(k\)-edge connected

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

2-node-connectivity network design ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming ⋮ 2-node-connectivity network design

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for access network design
• Min-max tree covers of graphs.
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Nowhere-zero 6-flows
• A constant-factor approximation algorithm for the \(k\)-MST problem
• Generalized submodular cover problems and applications
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems
• Approximating the Single-Sink Link-Installation Problem in Network Design
• Detecting high log-densities
• Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
• Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems
• Buy-at-Bulk Network Design with Protection
• Cost-Distance: Two Metric Network Design
• Survivable Network Design with Degree or Order Constraints
• Simpler and better approximation algorithms for network design
• Saving an epsilon
• Approximating Some Network Design Problems with Node Costs
• A Constant Factor Approximation for the Single Sink Edge Installation Problem
• Approximation Schemes for the Restricted Shortest Path Problem
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Bicriteria Network Design Problems
• Spanning Trees—Short or Small
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph