Approximation Algorithms for Single and Multi-Commodity Connected Facility Location

DOI10.1007/978-3-642-20807-2_20zbMath1341.90081OpenAlexW23104719MaRDI QIDQ3009767

Fabrizio Grandoni, Thomas Rothvoß

Publication date: 24 June 2011

Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20807-2_20

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (9)

Combinatorial approximation algorithms for the robust facility location problem with penalties ⋮ LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design ⋮ Combinatorial approximation algorithms for buy-at-bulk connected facility location problems ⋮ The connected facility location polytope ⋮ Approximate the lower-bounded connected facility location problem ⋮ LP-based approximation algorithms for facility location in buy-at-bulk network design ⋮ An algorithmic framework for the exact solution of tree-star problems ⋮ Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem ⋮ Computing a tree having a small vertex cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner tree problem on graphs: inapproximability results
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• Primal-dual algorithms for connected facility location problems
• Connected facility location via random facility sampling and core detouring
• An improved LP-based approximation for steiner tree
• Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
• A threshold of ln n for approximating set cover
• Cost-Distance: Two Metric Network Design
• New Approaches for Virtual Private Network Design
• Approximation via cost sharing
• Network Design via Core Detouring for Problems without a Core
• On the Complexity of the Asymmetric VPN Problem
• A Constant Factor Approximation for the Single Sink Edge Installation Problem
• Greedy Strikes Back: Improved Facility Location Algorithms
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• A constant-factor approximation for stochastic Steiner forest
• Provisioning a virtual private network
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithm Theory - SWAT 2004
• Improved Approximation for Single-Sink Buy-at-Bulk
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Approximation Algorithms for Single and Multi-Commodity Connected Facility Location