A 3-approximation algorithm for the k-level uncapacitated facility location problem

DOI10.1016/S0020-0190(99)00144-1MaRDI QIDQ1607016zbMATH OpenOpenAlexFDO

Authors Karen Aardal, F. Chudak, David B. Shmoys

Publication date 25 July 2002

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(99)00144-1

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Recommendations

• A 3-approximation algorithm for the facility location problem with uniform capacities
• An approximation algorithm for the \(k\)-level capacitated facility location problem
• An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
• A 3-approximation for facility location with uniform capacities
• A General k-Level Uncapacitated Facility Location Problem
• Improved approximation algorithm for k-level uncapacitated facility location problem (with penalties)
• Improved LP-rounding approximation algorithm for \(k\)-level uncapacitated facility location
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location

Cites work

• scientific article; zbMATH DE number 4202014 (Why is no real title available?)
• scientific article; zbMATH DE number 1187151 (Why is no real title available?)
• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 1303608 (Why is no real title available?)
• scientific article; zbMATH DE number 1305496 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Dual-Based Procedure for Dynamic Facility Location
• A Dual-Based Procedure for Uncapacitated Facility Location
• A Plant and Warehouse Location Problem
• A branch-and-bound algorithm for the multi-level uncapacitated facility location problem
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Geometric algorithms and combinatorial optimization
• On the Two-Level Uncapacitated Facility Location Problem

Cited in

(48)

• Robust network function virtualization
• Improved approximation algorithm for k-level uncapacitated facility location problem (with penalties)
• Approximating \(k\)-hop minimum spanning trees in Euclidean metrics
• An approximation algorithm for the \(k\)-level capacitated facility location problem
• A General k-Level Uncapacitated Facility Location Problem
• An approximation algorithm for the k-level concentrator location problem
• A \(k\)-product uncapacitated facility location problem
• The vendor location problem
• Approximating \(k\)-hop minimum-spanning trees
• Approximation algorithm for facility location with service installation costs
• A new approximation algorithm for the multilevel facility location problem
• Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems
• A new mixed integer linear programming model for the multi level uncapacitated facility location problem
• Multi-level facility location problems
• A cost-sharing scheme for the \(k\)-product facility location game with penalties
• An approximation algorithm for the k-level facility location problem with outliers
• Approximating the \(\tau\)-relaxed soft capacitated facility location problem
• Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
• A cross-monotonic cost sharing method for the facility location game with service installation costs
• Improved LP-rounding approximation algorithm for \(k\)-level uncapacitated facility location
• Improved approximation algorithms for multilevel facility location problems
• Approximation algorithm for resource allocation problems with time dependent penalties
• Multi-level facility location as the maximization of a submodular set function
• Inapproximability of the multi-level uncapacitated facility location problem
• Soft-capacitated facility location game
• An approximation algorithm for the maximization version of the two level uncapacitated facility location problem
• 2-level station location for bike sharing
• A review of hierarchical facility location models
• Approximating the two-level facility location problem via a quasi-greedy approach
• Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach
• An approximation algorithm for the k-level stochastic facility location problem
• Approximation Algorithms for the Multilevel Facility Location Problem with Linear/Submodular Penalties
• An approximate cost recovery scheme for the \(k\)-product facility location game with penalties
• A cost-sharing method for an uncapacitated facility location game with penalties
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• The \(k\)-level facility location game
• An improved approximation algorithm for the k-level facility location problem with soft capacities
• Algorithm for \(k\)-product facility location problem with submodular penalties
• An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
• Approximation algorithms for the dynamic \(k\)-level facility location problems
• A note on the maximization version of the multi-level facility location problem
• Combining very large scale and ILP based neighborhoods for a two-level location problem
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Approximation algorithms for \(k\)-level stochastic facility location problems
• Solving facility location problem based on duality approach
• A cost-sharing method for the multi-level economic lot-sizing game
• Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
• The facility location problem with maximum distance constraint

This page was built for publication: A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem

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