Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design

DOI10.1137/090750317zbMath1207.90019OpenAlexW2020400310MaRDI 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

zbMATH Keywords

approximation algorithmnetwork designnetwork floweconomies of scaleconcave costnonuniform buy-at-bulk

Mathematics Subject Classification ID

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

Related Items (14)

Minimum-Cost Network Design with (Dis)economies of Scale ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Online Buy-at-Bulk Network Design ⋮ APPROXIMATION ALGORITHMS FOR BUY-AT-BULK GEOMETRIC NETWORK DESIGN ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Pruning 2-connected graphs ⋮ Approximation algorithms for priority Steiner tree problems ⋮ Online covering with \(\ell_q\)-norm objectives and applications to network design ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ Spider Covering Algorithms for Network Design Problems ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Two-level hub Steiner trees ⋮ Approximability of capacitated network design

This page was built for publication: Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design