A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem
From MaRDI portal
Publication:1702823
DOI10.1007/s10878-017-0179-0zbMath1393.90103OpenAlexW2759640845MaRDI QIDQ1702823
Dongmei Zhang, Da-Chuan Xu, Lu Han, Dong-lei Du
Publication date: 1 March 2018
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-017-0179-0
Related Items
On stochastic \(k\)-facility location, Approximation algorithms for prize-collecting capacitated network design problems, Approximation schemes for \(k\)-facility location, An approximation algorithm for stochastic multi-level facility location problem with soft capacities
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 3-approximation algorithm for the facility location problem with uniform capacities
- Improved approximation algorithms for capacitated facility location problems
- A constant-factor approximation algorithm for the \(k\)-median problem
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- A new approximation algorithm for the \(k\)-facility location problem
- Approximation algorithms for hard capacitated \(k\)-facility location problems
- Approximating $k$-Median via Pseudo-Approximation
- An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- A new greedy approach for facility location problems
- Warehouse-Retailer Network Design Problem
- Comments on the note of Frieze
- An analysis of approximations for maximizing submodular set functions—I
- Greedy Strikes Back: Improved Facility Location Algorithms
- Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
- Analysis of a Local Search Heuristic for Facility Location Problems
- Local Search Heuristics for k-Median and Facility Location Problems
- Improved Combinatorial Algorithms for Facility Location Problems
- Stochastic Transportation-Inventory Network Design Problem
- On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
- Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
- An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem