LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design

DOI10.1007/978-3-319-21840-3_31zbMath1418.68243OpenAlexW2954234447MaRDI QIDQ3449835

Mohsen Rezapour, Mohammad R. Salavatipour, Jose A. Soto, Zachary Friggstad

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-21840-3_31

Mathematics Subject Classification ID

Integer programming (90C10) Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

Exact Approaches for Designing Multifacility Buy-at-Bulk Networks, LP-based approximation algorithms for facility location in buy-at-bulk network design

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual algorithms for connected facility location problems
• Balancing minimum spanning trees and shortest-path trees
• Connected facility location via random facility sampling and core detouring
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
• Cost-Distance: Two Metric Network Design
• Network Design via Core Detouring for Problems without a Core
• A constant factor approximation for the single sink edge installation problems
• Provisioning a virtual private network
• Algorithm Theory - SWAT 2004