An approximation algorithm for the k-level facility location problem with outliers

DOI10.1007/S11590-021-01701-8MaRDI QIDQ2047198zbMATH OpenOpenAlexFDO

Authors Lu Han, Dandan Liu, Dachuan Xu, Chenchen Wu

Publication date 19 August 2021

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-021-01701-8

zbMATH Keywords

outliersapproximation algorithmfacility location problemprimal-dual

Mathematics Subject Classification ID

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

Recommendations

• An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
• An approximation algorithm for the dynamic facility location problem with outliers
• Algorithms for facility location problems with outliers. (Extended abstract)
• An approximation algorithm for the \(k\)-level capacitated facility location problem
• Improved LP-rounding approximation algorithm for \(k\)-level uncapacitated facility location

Cites work

• scientific article; zbMATH DE number 1947060 (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?)
• scientific article; zbMATH DE number 1833402 (Why is no real title available?)
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
• A local search approximation algorithm for the \(k\)-means problem with penalties
• Algorithms for facility location problems with outliers. (Extended abstract)
• An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
• An approximation algorithm for the maximization version of the two level uncapacitated facility location problem
• 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 metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for the robust/soft-capacitated 2-level facility location problems
• Greedy Strikes Back: Improved Facility Location Algorithms
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved Combinatorial Algorithms for Facility Location Problems
• Improved approximation algorithm for k-level uncapacitated facility location problem (with penalties)
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Inapproximability of the multi-level uncapacitated facility location problem
• Local Search Heuristics for k-Median and Facility Location Problems
• Stochastic Transportation-Inventory Network Design Problem
• Warehouse-Retailer Network Design Problem

Cited in

(7)

• Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions
• An approximation algorithm for the dynamic facility location problem with outliers
• Constant Factor Approximation for Capacitated k-Center with Outliers
• Algorithms for facility location problems with outliers. (Extended abstract)
• An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties
• Approximation algorithms for the dynamic \(k\)-level facility location problems
• The facility location problem with maximum distance constraint

This page was built for publication: An approximation algorithm for the \(k\)-level facility location problem with outliers

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