Improved LP-rounding approximation algorithm for k-level uncapacitated facility location

DOI10.1007/978-3-642-31594-7_14MaRDI QIDQ2843244zbMATH OpenOpenAlexFDO

Authors Jaroslaw Byrka, Bartosz Rybicki

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31594-7_14

Mathematics Subject Classification ID

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

Recommendations

• Improved approximation algorithm for k-level uncapacitated facility location problem (with penalties)
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• An approximation algorithm for the k-level stochastic facility location problem
• An approximation algorithm for the k-level capacitated facility location problem

Cited in

(15)

• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• An improved approximation algorithm for the k-level facility location problem with soft capacities
• An LP-rounding based algorithm for a uniform capacitated facility location problem with penalties
• An approximation algorithm for the k-level facility location problem with outliers
• Approximation algorithms for the dynamic \(k\)-level facility location problems
• Two-level rectilinear Steiner trees
• Approximation algorithms for \(k\)-level stochastic facility location problems
• Improved approximation algorithm for k-level uncapacitated facility location problem (with penalties)
• Improved approximation algorithm for k-level UFL with penalties, a simplistic view on randomizing the scaling parameter
• A General k-Level Uncapacitated Facility Location Problem
• An approximation algorithm for the k-level concentrator location problem
• Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach
• Integrated Supply Chain Management via Randomized Rounding
• A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties
• Approximation algorithms for the robust/soft-capacitated 2-level facility location problems

This page was built for publication: Improved LP-rounding approximation algorithm for \(k\)-level uncapacitated facility location

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