An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
From MaRDI portal
Publication:5894066
DOI10.1137/070708901zbMath1205.90173OpenAlexW2769481137MaRDI QIDQ5894066
Publication date: 17 January 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/13979
Analysis of algorithms (68W40) Discrete location and assignment (90B80) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (59)
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties ⋮ Improved Approximation Algorithm for Fault-Tolerant Facility Placement ⋮ The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem ⋮ The online prize-collecting facility location problem ⋮ A cross-monotonic cost-sharing scheme for the concave facility location game ⋮ Bifactor approximation for location routing with vehicle and facility capacities ⋮ Approximation algorithms for \(k\)-level stochastic facility location problems ⋮ 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 ⋮ Perturbation resilience for the facility location problem ⋮ An approximation algorithm for the dynamic facility location problem with submodular penalties ⋮ Approximation algorithms for the fault-tolerant facility location problem with penalties ⋮ Approximation algorithm for squared metric facility location problem with nonuniform capacities ⋮ Approximation algorithms for the fault-tolerant facility location problem with submodular penalties ⋮ Approximation algorithms for median hub location problems ⋮ Unnamed Item ⋮ 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 ⋮ A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem ⋮ Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms ⋮ LP-Based Algorithms for Capacitated Facility Location ⋮ Unnamed Item ⋮ 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 ⋮ Integrated Supply Chain Management via Randomized Rounding ⋮ Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach ⋮ A cost-sharing method for an uncapacitated facility location game with penalties ⋮ Black-box reductions for cost-sharing mechanism design ⋮ LP-rounding algorithms for the fault-tolerant facility placement problem ⋮ An exact cooperative method for the uncapacitated facility location problem ⋮ Approximation algorithms for the robust facility leasing problem ⋮ A distributed O(1)-approximation algorithm for the uniform facility location problem ⋮ Fault-tolerant concave facility location problem with uniform requirements ⋮ Fast bounding procedures for large instances of the simple plant location problem ⋮ An improved per-scenario bound for the two-stage stochastic facility location problem ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ Facility location problems: a parameterized view ⋮ 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 ⋮ 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 \(k\)-level facility location problem with outliers ⋮ An approximation algorithm for the stochastic fault-tolerant facility location problem ⋮ Improved approximation algorithms for the facility location problems with linear/submodular penalties ⋮ A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems ⋮ Securely Connected Facility Location in Metric Graphs ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities ⋮ A cross-monotonic cost sharing method for the facility location game with service installation costs ⋮ Bounding quality of pure Nash equilibria in dual-role facility location games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithms for the stochastic priority facility location problem ⋮ Improved approximation algorithms for constrained fault-tolerant resource allocation ⋮ Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties) ⋮ Concave connection cost facility location and the star inventory routing problem
This page was built for publication: An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
