A 1.488 approximation algorithm for the uncapacitated facility location problem
From MaRDI portal
Publication:1951570
DOI10.1016/j.ic.2012.01.007zbMath1281.68236OpenAlexW2177090493MaRDI QIDQ1951570
Publication date: 6 June 2013
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2012.01.007
Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items (78)
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties ⋮ From Cost Sharing Mechanisms to Online Selection Problems ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Improved Approximation Algorithm for Fault-Tolerant Facility Placement ⋮ The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem ⋮ Combinatorial approximation algorithms for buy-at-bulk connected facility location problems ⋮ The online prize-collecting facility location problem ⋮ On stochastic \(k\)-facility location ⋮ Analysis of a local search algorithm for the k-facility location problem ⋮ A lower bound for metric 1-median selection ⋮ Efficient sensor network management for asset localization ⋮ Bifactor approximation for location routing with vehicle and facility capacities ⋮ LP-based approximation for uniform capacitated facility location problem ⋮ Approximating Airports and Railways ⋮ An Approximation Algorithm for the Two-Stage Distributionally Robust Facility Location Problem ⋮ Perturbation resilience for the facility location problem ⋮ Two-phase semi-Lagrangian relaxation for solving the uncapacitated distribution centers location problem for B2C E-commerce ⋮ Approximation algorithms for the individually fair \(k\)-center with outliers ⋮ An approximation algorithm for the dynamic facility location problem with submodular penalties ⋮ Robust network function virtualization ⋮ Problem-driven scenario clustering in stochastic optimization ⋮ 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 ⋮ The facility location problem with maximum distance constraint ⋮ Approximation algorithms for median hub location problems ⋮ Approximation algorithm for squared metric two-stage stochastic facility location problem ⋮ Unnamed Item ⋮ \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate the lower-bounded connected facility location problem ⋮ An approximation algorithm for the \(k\)-median warehouse-retailer network design problem ⋮ Dynamic Sum-Radii Clustering ⋮ Unnamed Item ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ On the cost of essentially fair clusterings ⋮ Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties ⋮ Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming ⋮ Approximation algorithms for the robust facility leasing problem ⋮ On the Facility Location Problem in Online and Dynamic Models. ⋮ A per-scenario bound for the two-stage stochastic facility location problem with linear penalty ⋮ Supply Chain Management with Online Customer Selection ⋮ Unnamed Item ⋮ Approximation algorithms for the lower-bounded \(k\)-median and its generalizations ⋮ Local search approximation algorithms for the sum of squares facility location problems ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ Unnamed Item ⋮ 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 ⋮ An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme ⋮ Mixed fault tolerance in server assignment: combining reinforcement and backup ⋮ Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems ⋮ A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem ⋮ 2-level station location for bike sharing ⋮ Approximation algorithms for the lower-bounded knapsack median problem ⋮ LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem ⋮ An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties ⋮ An approximation algorithm for the \(k\)-level facility location problem with outliers ⋮ 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 ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem ⋮ Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties)
This page was built for publication: A 1.488 approximation algorithm for the uncapacitated facility location problem
