A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties

DOI10.1007/s10878-012-9540-5zbMath1296.90072MaRDI QIDQ2015801

Yu Li, Nai-Hua Xiu, Da-Chuan Xu, Dong-lei Du

Publication date: 24 June 2014

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9540-5

zbMATH Keywords

linear programming; approximation algorithm; submodular function; facility location problem

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90B80: Discrete location and assignment

Related Items

An approximation algorithm for submodular hitting set problem with linear penalties

Cites Work

• Approximation algorithms for supply chain planning and logistics problems with market choice
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• Submodular functions and optimization.
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• Approximation Algorithms for Metric Facility Location Problems
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item