Approximation algorithms for nonuniform buy-at-bulk network design

DOI10.1137/090750317MaRDI QIDQ3053149zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Mohammad Salavatipour, Mohammad T. Hajiaghayi, Guy Kortsarz

Publication date 4 November 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/090750317

zbMATH Keywords

approximation algorithmconcave costeconomies of scalenetwork designnetwork flownonuniform buy-at-bulk

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On non-uniform multicommodity buy-at-bulk network design
• Approximation algorithms for node-weighted buy-at-bulk network design
• Improved Approximation for Single-Sink Buy-at-Bulk
• Approximating directed buy-at-bulk network design
• Algorithm Theory - SWAT 2004

Cited in

(38)

• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Improved approximation algorithms for the single-sink buy-at-bulk network design problems
• Approximation algorithms for the max-buying problem with limited supply
• A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design
• Two-level hub Steiner trees
• Online covering with \(\ell_q\)-norm objectives and applications to network design
• Approximability of capacitated network design
• Pruning 2-connected graphs
• Approximation algorithms for priority Steiner tree problems
• Approximation algorithms for node-weighted buy-at-bulk network design
• Approximating directed buy-at-bulk network design
• Oblivious buy-at-bulk in planar graphs
• Buy-at-bulk network design with protection
• Approximation Algorithms for Buy-at-Bulk Geometric Network Design
• Approximation algorithms for buy-at-bulk geometric network design
• Cost-Distance: Two Metric Network Design
• Minimum-cost network design with (dis)economies of scale
• Approximation via cost sharing
• On non-uniform multicommodity buy-at-bulk network design
• Improved approximation algorithms for directed Steiner forest
• scientific article; zbMATH DE number 2079376 (Why is no real title available?)
• LAST but not least: online spanners for buy-at-bulk
• Online Buy-at-Bulk Network Design
• Spider covering algorithms for network design problems
• Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems
• A New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design
• Hallucination helps: energy efficient virtual circuit routing
• Algorithm Theory - SWAT 2004
• Improved Approximation for Single-Sink Buy-at-Bulk
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Buy-at-bulk facility location on trees
• Simple approximations for general spanner problems
• The Steiner path aggregation problem
• Approximation algorithms for access network design
• Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing
• Directed buy-at-bulk spanners
• Traffic-oblivious multi-commodity flow network design
• Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk

This page was built for publication: Approximation algorithms for nonuniform buy-at-bulk network design

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