An improved approximation algorithm for uncapacitated facility location problem with penalties
From MaRDI portal
Publication:1029272
DOI10.1007/s10878-007-9127-8zbMath1165.90550OpenAlexW2083653011MaRDI QIDQ1029272
Publication date: 10 July 2009
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-007-9127-8
Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)
Related Items
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties, Combinatorial approximation algorithms for the robust facility location problem with penalties, Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions, The online prize-collecting facility location problem, A $$(5.83+\epsilon )$$ ( 5.83 + ϵ ) -Approximation Algorithm for Universal Facility Location Problem with Linear Penalties, Approximation algorithm for uniform bounded 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 dynamic facility location problem with submodular penalties, Approximation algorithms for the fault-tolerant facility location problem with penalties, Approximation algorithms for prize-collecting capacitated network design problems, The facility location problem with maximum distance constraint, Improved approximation algorithm for universal facility location problem with linear penalties, A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Approximation algorithms for the priority facility location problem with penalties, Unnamed Item, A cost-sharing method for an uncapacitated facility location game with penalties, Approximation Algorithm for the Uniform Bounded Facility Problem, Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties, Approximation Algorithms for Single and Multi-Commodity Connected Facility Location, Local search algorithm for universal facility location problem with linear penalties, A per-scenario bound for the two-stage stochastic facility location problem with linear penalty, Supply Chain Management with Online Customer Selection, A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties, An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties, Improved approximation algorithms for the facility location problems with linear/submodular penalties, Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties), Concave connection cost facility location and the star inventory routing problem
Cites Work
- An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- 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 constant factor approximation algorithm for the fault-tolerant facility location problem
- Local search heuristic for k-median and facility location problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
