On facility location with general lower bounds

DOI10.1137/1.9781611975482.138zbMATH Open1432.68580arXiv1805.02244OpenAlexW2799689005MaRDI QIDQ5236325FDOQ5236325

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)

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.

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

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

Mathematics Subject Classification ID

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

Cited In (16)

• Facility Location with Matroid or Knapsack Constraints
• A localization property for facility-location problems with arbitrary norms
• Upper Bound for the Competitive Facility Location Problem with Quantile Criterion
• Title not available (Why is that?)
• Lower and upper bounds for the continuous single facility location problem in the presence of a forbidden region and travel barrier
• Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
• Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
• Approximation algorithms for the lower-bounded knapsack median problem
• On the Weber facility location problem with limited distances and side constraints
• Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation
• An improved lower bound for the multimedian location problem
• Approximate the lower-bounded connected facility location problem
• An approximation algorithm for stochastic multi-level facility location problem with soft capacities
• Respecting lower bounds in uniform lower and upper bounded facility location problem
• Borda winner in facility location problems on sphere
• Approximation algorithms for the lower bounded correlation clustering 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)