An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme

DOI10.1007/s10878-016-0080-2zbMath1402.90159OpenAlexW2521482842MaRDI QIDQ724755

Yishui Wang, Da-Chuan Xu, Dong-lei Du, Chen-Chen Wu

Publication date: 26 July 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-016-0080-2

zbMATH Keywords

approximation algorithmlocal search\(k\)-facility locationlinear penalties

Mathematics Subject Classification ID

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

Related Items (7)

An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution ⋮ Local search approximation algorithms for the \(k\)-means problem with penalties ⋮ Approximation schemes for \(k\)-facility location ⋮ Capacitated facility location with outliers/penalties ⋮ A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties ⋮ Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties ⋮ Approximation algorithms for the lower-bounded \(k\)-median and its generalizations

Cites Work

• Unnamed Item
• A survey on offline scheduling with rejection
• A note on the prize collecting traveling salesman problem
• Local search algorithms for the red-blue median problem
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A new approximation algorithm for the \(k\)-facility location problem
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties
• 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
• Heuristics for the fixed cost median problem
• Local Search Heuristics for k-Median and Facility Location Problems
• Multiprocessor Scheduling with Rejection
• Improved Combinatorial Algorithms for Facility Location Problems

This page was built for publication: An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme