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

DOI10.1007/S00224-014-9575-3MaRDI QIDQ260252zbMATH OpenOpenAlexWikidataFDO

Authors Jaroslaw Byrka, Shanfei Li, Bartosz Rybicki

Publication date 21 March 2016

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

approximation algorithmsfacility location

Mathematics Subject Classification ID

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

Recommendations

• 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
• An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• An improved approximation algorithm for uncapacitated facility location problem with penalties

Cites work

• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• Algorithms for facility location problems with outliers. (Extended abstract)
• An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• Approximating the two-level facility location problem via a quasi-greedy approach
• Approximation algorithms for supply chain planning and logistics problems with market choice
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Greedy Strikes Back: Improved Facility Location Algorithms
• scientific article; zbMATH DE number 1303564 (Why is no real title available?)
• scientific article; zbMATH DE number 2038706 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 2086926 (Why is no real title available?)
• Improved approximation algorithm for k-level UFL with penalties, a simplistic view on randomizing the scaling parameter
• Improved approximation algorithms for the facility location problems with linear/submodular penalty
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved LP-rounding approximation algorithm for k-level uncapacitated facility location
• Inapproximability of the multi-level uncapacitated facility location problem

Cited in

(15)

• An improved approximation algorithm for uncapacitated facility location problem with penalties
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• Multi-level facility location problems
• Approximating the \(\tau\)-relaxed soft capacitated facility location problem
• An approximation algorithm for the k-level facility location problem with outliers
• An acceleration of Erlenkotter-Körkel's algorithms for the uncapacitated facility location problem
• Automatic tracking and positioning algorithm for moving targets in complex environment
• Approximation algorithms for \(k\)-level stochastic facility location problems
• 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
• An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
• Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
• Covering clients with types and budgets
• Computing and Combinatorics
• Robust network function virtualization

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q260252)