A new approximation algorithm for the multilevel facility location problem

DOI10.1016/j.dam.2009.11.007zbMath1185.90158OpenAlexW2109353682MaRDI QIDQ968163

Adriana F. Gabor, Jan-Kees C. W. van Ommeren

Publication date: 5 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/a-new-approximation-algorithm-for-the-multilevel-facility-location-problem(4bb5eda0-3411-4f9a-891a-80d656f19f6e).html

zbMATH Keywords

facility locationapproximation algorithmsrandomized algorithms

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Related Items (14)

Exactly solving a two-level location problem with modular node capacities ⋮ A new mixed integer linear programming model for the multi level uncapacitated facility location problem ⋮ Approximation Algorithms for the Multilevel Facility Location Problem with Linear/Submodular Penalties ⋮ An approximation algorithm for the \(k\)-level stochastic facility location problem ⋮ An improved approximation algorithm for the \(k\)-level facility location problem with soft capacities ⋮ An approximation algorithm for the \(k\)-level concentrator location problem ⋮ Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location ⋮ Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach ⋮ Approximation algorithms for the robust/soft-capacitated 2-level facility location problems ⋮ Multi-level facility location problems ⋮ The vendor location problem ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities ⋮ Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks ⋮ Unnamed Item

Cites Work

• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• Improved approximation algorithms for multilevel facility location problems
• Approximating the two-level facility location problem via a quasi-greedy approach
• Cost-Distance: Two Metric Network Design
• 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
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
• Local search heuristic for k-median and facility location problems
• On the Two-Level Uncapacitated Facility Location Problem
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A new approximation algorithm for the multilevel facility location problem