On facility location with general lower bounds

DOI10.1137/1.9781611975482.138MaRDI QIDQ5236325zbMATH OpenOpenAlexFDO

Authors Shi Li

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.02244

Mathematics Subject Classification ID

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

Abstract: In this paper, we give the first constant approximation algorithm for the lower bounded facility location (LBFL) problem with general lower bounds. Prior to our work, such algorithms were only known for the special case where all facilities have the same lower bound: Svitkina cite{Svi10} gave a $448$-approximation for the special case, and subsequently Ahmadian and Swamy cite{AS13} improved the approximation factor to 82.6. As in cite{Svi10} and cite{AS13}, our algorithm for LBFL with general lower bounds works by reducing the problem to the capacitated facility location (CFL) problem. To handle some challenges caused by the general lower bounds, our algorithm involves more reduction steps. One main complication is that after aggregation of clients and facilities at a few locations, each of these locations may contain many facilities with different opening costs and lower bounds. To handle this issue, we introduce and reduce our LBFL problem to an intermediate problem called the transportation with configurable supplies and demands (TCSD) problem, which in turn can be reduced to the CFL problem.

Recommendations

• Lower-bounded facility location
• Improved approximation guarantees for lower-bounded facility location
• scientific article; zbMATH DE number 6263680
• Approximating connected facility location with lower and upper bounds via LP rounding
• Approximation algorithm for uniform bounded facility location problem

Cited in

(19)

• An improved lower bound for the multimedian location problem
• Upper Bound for the Competitive Facility Location Problem with Quantile Criterion
• Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
• Approximation algorithms for the lower-bounded knapsack median problem
• Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
• Approximating connected facility location with lower and upper bounds via LP rounding
• Borda winner in facility location problems on sphere
• Approximation algorithms for the lower bounded correlation clustering problem
• scientific article; zbMATH DE number 7765379 (Why is no real title available?)
• An approximation algorithm for stochastic multi-level facility location problem with soft capacities
• Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation
• Facility Location with Matroid or Knapsack Constraints
• Improved approximation guarantees for lower-bounded facility location
• A localization property for facility-location problems with arbitrary norms
• Lower and upper bounds for the continuous single facility location problem in the presence of a forbidden region and travel barrier
• Approximate the lower-bounded connected facility location problem
• On the Weber facility location problem with limited distances and side constraints
• Lower-bounded facility location
• Respecting lower bounds in uniform lower and upper bounded facility location problem

This page was built for publication: On facility location with general lower bounds

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