Approximating the \(\tau\)-relaxed soft capacitated facility location problem

DOI10.1007/s10878-020-00631-yzbMath1466.90046OpenAlexW3046897263MaRDI 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

zbMATH Keywords

approximation algorithmfacility location problemprimal-dualrelaxed triangle inequalitysoft capacitated

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (1)

Approximate the lower-bounded connected facility location problem

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

This page was built for publication: Approximating the \(\tau\)-relaxed soft capacitated facility location problem