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

DOI10.1007/s10878-012-9540-5zbMath1296.90072OpenAlexW2057791178MaRDI 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 programmingapproximation algorithmsubmodular functionfacility location problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)

Related Items (1)

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

This page was built for publication: A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties