Approximation algorithms for soft-capacitated facility location in capacitated network design

DOI10.1007/s00453-007-9032-7zbMath1181.90171OpenAlexW2072770591MaRDI QIDQ1024778

Bo Chen, Xu-jin Chen

Publication date: 17 June 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9032-7

zbMATH Keywords

approximation algorithmfacility locationnetwork designperformance guaranteesoft capacity

Mathematics Subject Classification ID

Continuous location (90B85) Approximation algorithms (68W25)

Related Items

Combinatorial approximation algorithms for the robust facility location problem with penalties, Bifactor approximation for location routing with vehicle and facility capacities, An Approximation Algorithm for the Two-Stage Distributionally Robust Facility Location Problem, Approximation Algorithms for the Robust Facility Location Problem with Penalties, An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties, An approximation algorithm for the \(k\)-level stochastic facility location problem, A cost-sharing method for the multi-level economic lot-sizing game, An approximation algorithm for the dynamic facility location problem with outliers, Approximation algorithms for the fault-tolerant facility location problem with penalties, Approximation algorithms for the priority facility location problem with penalties, An approximation algorithm for soft capacitated \(k\)-facility location problem, Improved approximation algorithms for the robust fault-tolerant facility location problem, A primal-dual approximation algorithm for stochastic facility location problem with service installation costs, An approximation algorithm for the \(k\)-median warehouse-retailer network design problem, Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach, Fault-tolerant concave facility location problem with uniform requirements, A per-scenario bound for the two-stage stochastic facility location problem with linear penalty, An improved per-scenario bound for the two-stage stochastic facility location problem, A local search approximation algorithm for a squared metric \(k\)-facility location problem, LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem, An approximation algorithm for the stochastic fault-tolerant facility location problem, Improved approximation algorithms for the facility location problems with linear/submodular penalties, A primal-dual -approximation algorithm for the stochastic facility location problem with submodular penalties, Approximation algorithms for the stochastic priority facility location problem

Cites Work

• Approximation algorithms for a capacitated network design problem
• Primal-dual algorithms for connected facility location problems
• Approximation Algorithms for Problems Combining Facility Location and Network Design
• Approximation Algorithms for Metric Facility Location Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy Strikes Back: Improved Facility Location Algorithms
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Unnamed Item
• Unnamed Item
• Unnamed Item