An LP rounding algorithm for approximating uncapacitated facility location problem with penalties

DOI10.1016/j.ipl.2005.01.005zbMath1177.90257OpenAlexW2000500966MaRDI QIDQ1041733

Jinhui Xu, Guang Xu

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.01.005

zbMATH Keywords

outliersalgorithmsapproximation algorithmsfacility location problem

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (23)

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 ⋮ A $$(5.83+\epsilon )$$ ( 5.83 + ϵ ) -Approximation Algorithm for Universal Facility Location Problem with Linear Penalties ⋮ 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 ⋮ 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 priority facility location problem with penalties ⋮ Unnamed Item ⋮ A cost-sharing method for an uncapacitated facility location game with penalties ⋮ Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties ⋮ 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 ⋮ Min sum clustering with penalties ⋮ A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties ⋮ An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties ⋮ Improved approximation algorithms for the facility location problems with linear/submodular penalties ⋮ An improved approximation algorithm for uncapacitated facility location problem with 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

• Approximation algorithms for geometric median problems
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Local search heuristic for k-median and facility location problems
• Improved Combinatorial Algorithms for Facility Location Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An LP rounding algorithm for approximating uncapacitated facility location problem with penalties