Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
From MaRDI portal
Publication:3053149
DOI10.1137/090750317zbMath1207.90019MaRDI QIDQ3053149
Chandra Chekuri, Mohammad R. Salavatipour, Mohammad Taghi 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
approximation algorithm; network design; network flow; economies of scale; concave cost; nonuniform buy-at-bulk
90C60: Abstract computational complexity for mathematical programming problems
90C59: Approximation methods and heuristics in mathematical programming
90B10: Deterministic network models in operations research
90C27: Combinatorial optimization
Related Items
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, Hallucination Helps: Energy Efficient Virtual Circuit Routing, Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph, Improved approximation algorithms for directed Steiner forest, 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 BUY-AT-BULK GEOMETRIC NETWORK DESIGN, Minimum-Cost Network Design with (Dis)economies of Scale