A $$(5.83+\epsilon )$$ ( 5.83 + ϵ ) -Approximation Algorithm for Universal Facility Location Problem with Linear Penalties

DOI10.1007/978-3-319-26626-8_6zbMath1453.90098OpenAlexW2293751504MaRDI QIDQ3467835

Yicheng Xu, Dong-lei Du, Da-Chuan Xu, Chen-Chen Wu

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_6

zbMATH Keywords

approximation algorithmlocal searchpenaltyuniversal facility location

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
• Improved local search for universal facility location
• From stars to comets: improved local search for universal facility location
• LP-Based Algorithms for Capacitated Facility Location
• A 3-Approximation for Facility Location with Uniform Capacities
• Analysis of a Local Search Heuristic for Facility Location Problems
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• Algorithms - ESA 2003