Inapproximability of the multilevel uncapacitated facility location problem

DOI10.1145/2907050MaRDI QIDQ4962635zbMATH OpenOpenAlexFDO

Authors Ravishankar Krishnaswamy, Maxim Sviridenko

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2907050

zbMATH Keywords

approximation algorithmshardness of approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• Inapproximability of the multi-level uncapacitated facility location problem
• Improved approximation algorithms for multilevel facility location problems
• scientific article; zbMATH DE number 1947043
• An approximation algorithm for the k-level capacitated facility location problem
• A General k-Level Uncapacitated Facility Location Problem

Cited in

(5)

• Multi-level facility location problems
• An approximation algorithm for stochastic multi-level facility location problem with soft capacities
• Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
• Inapproximability of the multi-level uncapacitated facility location problem
• A polynomial-time exact algorithm for the connected k-facility location problem on trees

This page was built for publication: Inapproximability of the multilevel uncapacitated facility location problem

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