A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design

DOI10.1007/S10878-012-9544-1MaRDI QIDQ2015804zbMATH OpenOpenAlexFDO

Authors Peng Zhang

Publication date 24 June 2014

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

Full work available at URL https://doi.org/10.1007/s10878-012-9544-1

zbMATH Keywords

linear programmingapproximation algorithmnetwork designbuy-at-bulk

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39)

Recommendations

• A New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design
• Improved Approximation for Single-Sink Buy-at-Bulk
• Improved approximation algorithms for the single-sink buy-at-bulk network design problems
• Algorithm Theory - SWAT 2004
• Approximation algorithms for nonuniform buy-at-bulk network design

Cites work

• scientific article; zbMATH DE number 2089220 (Why is no real title available?)
• scientific article; zbMATH DE number 1003287 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1757956 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 2086941 (Why is no real title available?)
• scientific article; zbMATH DE number 6472639 (Why is no real title available?)
• A New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design
• A constant factor approximation for the single sink edge installation problems
• A tight bound on approximating arbitrary metrics by tree metrics
• Algorithm Theory - SWAT 2004
• An approximation algorithm for the generalized \(k\)-multicut problem
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• Approximation algorithms for nonuniform buy-at-bulk network design
• Approximation via cost sharing
• Connected facility location via random facility sampling and core detouring
• Deterministic sampling algorithms for network design
• Improved Approximation for Single-Sink Buy-at-Bulk
• Network design via core detouring for problems without a core
• New Approaches for Virtual Private Network Design
• On non-uniform multicommodity buy-at-bulk network design
• On the approximability of some network design problems
• Provisioning a virtual private network: a network design problem for multicommodity flow
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Simpler and better approximation algorithms for network design
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema

Cited in

(3)

• One tree suffices: a simultaneous \(O(1)\)-approximation for single-sink buy-at-bulk
• Improved approximation algorithms for the single-sink buy-at-bulk network design problems
• A New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design

This page was built for publication: A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design

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