Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties)

DOI10.1007/s00224-014-9575-3zbMath1336.68290OpenAlexW2021745860WikidataQ59473356 ScholiaQ59473356MaRDI QIDQ260252

Shanfei Li, Bartosz Rybicki, Jaroslaw Byrka

Publication date: 21 March 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9575-3

zbMATH Keywords

facility locationapproximation algorithms

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (7)

Approximation algorithms for \(k\)-level stochastic facility location problems ⋮ Robust network function virtualization ⋮ Multi-level facility location problems ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ Unnamed Item ⋮ An approximation algorithm for the \(k\)-level facility location problem with outliers ⋮ Automatic tracking and positioning algorithm for moving targets in complex environment

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 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Approximating the two-level facility location problem via a quasi-greedy approach
• Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location
• Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties)