LP-based approximation algorithms for facility location in buy-at-bulk network design

DOI10.1007/s00453-018-0458-xzbMath1418.68242OpenAlexW2805325553WikidataQ129756160 ScholiaQ129756160MaRDI QIDQ666665

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

Publication date: 11 March 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0458-x

zbMATH Keywords

approximation algorithmfacility locationbuy-at-bulk network designLP rounding

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial approximation algorithms for buy-at-bulk connected facility location problems
• 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
• From Uncertainty to Nonlinearity: Solving Virtual Private Network via Single-Sink Buy-at-Bulk
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
• Approximation Algorithms for Problems Combining Facility Location and Network Design
• Cost-Distance: Two Metric Network Design
• LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design
• Network Design via Core Detouring for Problems without a Core
• A Constant Factor Approximation for the Single Sink Edge Installation Problem
• Provisioning a virtual private network
• Algorithm Theory - SWAT 2004

This page was built for publication: LP-based approximation algorithms for facility location in buy-at-bulk network design