Approximating the \(\tau\)-relaxed soft capacitated facility location problem
From MaRDI portal
Publication:2023133
DOI10.1007/s10878-020-00631-yzbMath1466.90046MaRDI QIDQ2023133
Yicheng Xu, Lu Han, Dongmei Zhang, Da-Chuan Xu
Publication date: 3 May 2021
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-020-00631-y
approximation algorithm; facility location problem; primal-dual; relaxed triangle inequality; soft capacitated
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
90B80: Discrete location and assignment
68W25: Approximation algorithms
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties)
- An approximation algorithm for the stochastic fault-tolerant facility location problem
- Improved approximation algorithms for the facility location problems with linear/submodular penalties
- A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems
- Approximation algorithms for geometric median problems
- A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
- A constant-factor approximation algorithm for the \(k\)-median problem
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space
- Approximation Algorithms for Metric Facility Location Problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Warehouse-Retailer Network Design Problem
- Heuristics for the fixed cost median problem
- Greedy Strikes Back: Improved Facility Location Algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
- Local Search Heuristics for k-Median and Facility Location Problems
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
- Stochastic Transportation-Inventory Network Design Problem
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
