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 algorithmnetwork flownetwork designeconomies of scaleconcave costnonuniform buy-at-bulk

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) 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

(32)

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

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)