Approximation Algorithms for Metric Facility Location Problems
From MaRDI portal
Publication:3434992
DOI10.1137/S0097539703435716zbMath1151.90590OpenAlexW1973529814MaRDI QIDQ3434992
Yinyu Ye, Mohammad Mahdian, Jia-Wei Zhang
Publication date: 3 May 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539703435716
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80)
Related Items (67)
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties ⋮ Beyond Moulin mechanisms ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ The online prize-collecting facility location problem ⋮ Approximation algorithm for uniform bounded facility location problem ⋮ 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 ⋮ An approximation algorithm for the \(k\)-level capacitated facility location problem ⋮ An approximation algorithm for the dynamic facility location problem with submodular penalties ⋮ 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 fault-tolerant facility location problem with submodular penalties ⋮ The facility location problem with maximum distance constraint ⋮ Recovery guarantees for exemplar-based clustering ⋮ A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties ⋮ Approximation Algorithms for Stochastic and Risk-Averse Optimization ⋮ A primal-dual approximation algorithm for the facility location problem with submodular penalties ⋮ Approximation algorithms for the fault-tolerant facility placement problem ⋮ 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 ⋮ A continuation approach for the capacitated multi-facility weber problem based on nonlinear SOCP reformulation ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Dynamic Sum-Radii Clustering ⋮ Approximation algorithm for facility location with service installation costs ⋮ Capacitated Domination Problem ⋮ Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach ⋮ LP-based approximation algorithms for capacitated facility location ⋮ A cost-sharing method for an uncapacitated facility location game with penalties ⋮ Black-box reductions for cost-sharing mechanism design ⋮ Approximation Algorithm for the Uniform Bounded Facility Problem ⋮ An exact cooperative method for the uncapacitated facility location problem ⋮ Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties ⋮ A mixed integer programming formulation and solution for traffic analysis zone delineation considering zone amount decision ⋮ A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem ⋮ Robust fault tolerant uncapacitated facility location ⋮ Approximating soft-capacitated facility location problem with uncertainty ⋮ A distributed O(1)-approximation algorithm for the uniform facility location problem ⋮ Fault-tolerant concave facility location problem with uniform requirements ⋮ A per-scenario bound for the two-stage stochastic facility location problem with linear penalty ⋮ Capacitated domination problem ⋮ Fast bounding procedures for large instances of the simple plant location problem ⋮ A new approximation algorithm for the multilevel facility location problem ⋮ Deterministic sampling algorithms for network design ⋮ Soft-capacitated facility location game ⋮ A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties ⋮ An improved per-scenario bound for the two-stage stochastic facility location problem ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ Cost-effective designs of fault-tolerant access networks in communication systems ⋮ Integrating facility location and production planning decisions ⋮ A local search approximation algorithm for a squared metric \(k\)-facility location problem ⋮ Approximation algorithms for the transportation problem with market choice and related models ⋮ Mixed fault tolerance in server assignment: combining reinforcement and backup ⋮ A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem ⋮ Approximating $k$-Median via Pseudo-Approximation ⋮ 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 cost-sharing method for an economic lot-sizing game ⋮ A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems ⋮ Approximation algorithms for soft-capacitated facility location in capacitated network design ⋮ A cross-monotonic cost sharing method for the facility location game with service installation costs ⋮ Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks ⋮ Unnamed Item ⋮ Approximation algorithms for the stochastic priority facility location problem ⋮ Improved approximation algorithms for constrained fault-tolerant resource allocation
This page was built for publication: Approximation Algorithms for Metric Facility Location Problems
