An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties

DOI10.1007/978-3-540-89985-3_6zbMath1188.68355OpenAlexW103195536MaRDI QIDQ3628452

Mohammad Ghodsi, Ali Niknafs, Mohsen Asadi

Publication date: 20 May 2009

Published in: Communications in Computer and Information Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-89985-3_6

zbMATH Keywords

facility locationuncapacitated facility location\(k\)-level facility locationfacility location with outliers

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items (5)

A cost-sharing scheme for the \(k\)-level facility location game with penalties ⋮ Approximation Algorithms for the Multilevel Facility Location Problem with Linear/Submodular Penalties ⋮ Multi-level facility location problems ⋮ An approximation algorithm for the \(k\)-level facility location problem with outliers ⋮ Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A review of hierarchical facility location models
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• The \(k\)-level facility location game
• 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
• Local search heuristic for k-median and facility location problems
• Theory and Applications of Models of Computation

This page was built for publication: An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties