An approximation algorithm for soft capacitated \(k\)-facility location problem

DOI10.1007/s10878-017-0192-3zbMath1394.90484OpenAlexW2766583685MaRDI QIDQ1702830

Yanjun Jiang, Da-Chuan Xu, Chen-Chen Wu, Dongmei Zhang, 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-0192-3

zbMATH Keywords

approximation algorithmprimal-dual schemesoft capacitated \(k\)-facility location problem

Mathematics Subject Classification ID

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

Related Items

Approximation schemes for \(k\)-facility location

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for soft-capacitated facility location in capacitated network design
• A new approximation algorithm for the \(k\)-facility location problem
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• Approximation algorithms for hard capacitated \(k\)-facility location problems
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
• Approximation Algorithms for Metric Facility Location Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A 3-Approximation for Facility Location with Uniform Capacities
• Greedy Strikes Back: Improved Facility Location Algorithms
• Approximating capacitated k-median with (1 + ∊)k open facilities
• Improved Combinatorial Approximation Algorithms for the k-Level Facility Location 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
• Approximating k-median via pseudo-approximation
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem

This page was built for publication: An approximation algorithm for soft capacitated \(k\)-facility location problem