An improved approximation algorithm for uncapacitated facility location problem with penalties

DOI10.1007/s10878-007-9127-8zbMath1165.90550MaRDI QIDQ1029272

Jinhui Xu, Guang Xu

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

zbMATH Keywords

outliers; algorithms; approximation algorithms; facility location problem

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90B80: Discrete location and assignment

Related Items

Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties, 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 prize-collecting capacitated network design problems, The facility location problem with maximum distance constraint, A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties, Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties), Combinatorial approximation algorithms for the robust facility location problem with penalties, The online prize-collecting facility location problem, 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, A cost-sharing method for an uncapacitated facility location game with penalties, Local search algorithm for universal facility location problem with linear penalties, Improved approximation algorithms for the facility location problems with linear/submodular penalties, Approximation algorithms for the priority facility location problem with penalties, Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions, 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, Concave connection cost facility location and the star inventory routing problem, An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties, Approximation algorithm for uniform bounded facility location problem, Approximation algorithms for the fault-tolerant facility location problem with penalties, Improved approximation algorithm for universal facility location problem with linear penalties, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Approximation Algorithms for the Robust Facility Location Problem with Penalties, Approximation Algorithm for the Uniform Bounded Facility Problem, Approximation Algorithms for Single and Multi-Commodity Connected Facility Location, A $$(5.83+\epsilon )$$ ( 5.83 + ϵ ) -Approximation Algorithm for Universal Facility Location Problem with Linear Penalties

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