Approximation algorithm for facility location with service installation costs

DOI10.1016/j.orl.2007.04.002zbMath1138.90040OpenAlexW1988593260MaRDI QIDQ924885

Da-Chuan Xu, Shu-Zhong Zhang

Publication date: 29 May 2008

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2007.04.002

zbMATH Keywords

approximation algorithmfacility locationlinear programming relaxation

Mathematics Subject Classification ID

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

Related Items (11)

A new mixed integer linear programming model for the multi level uncapacitated facility location problem ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ An approximation algorithm for the \(k\)-level capacitated facility location problem ⋮ An approximation algorithm for the dynamic facility location problem with submodular penalties ⋮ A primal-dual approximation algorithm for the facility location problem with submodular penalties ⋮ A primal-dual approximation algorithm for stochastic facility location problem with service installation costs ⋮ A cost-sharing method for an uncapacitated facility location game with penalties ⋮ Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties ⋮ Soft-capacitated facility location game ⋮ A cross-monotonic cost sharing method for the facility location game with service installation costs ⋮ Approximation algorithms for the stochastic priority facility location problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• A note on the maximization version of the multi-level facility location problem
• The \(k\)-level facility location game
• Approximating the two-level facility location problem via a quasi-greedy approach
• Approximation Algorithms for Metric Facility Location Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
• Improved Combinatorial Algorithms for Facility Location Problems
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

This page was built for publication: Approximation algorithm for facility location with service installation costs