Local search approximation algorithms for the sum of squares facility location problems

DOI10.1007/s10898-018-00733-2zbMath1426.90183OpenAlexW2908427515MaRDI QIDQ2274862

Peng Zhang, Dongmei Zhang, Yishui Wang, Zhenning Zhang, Da-Chuan Xu

Publication date: 1 October 2019

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

Full work available at URL: https://doi.org/10.1007/s10898-018-00733-2

zbMATH Keywords

approximation algorithmlocal searchfacility location\(K\)-means

Mathematics Subject Classification ID

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

Related Items (1)

Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties

Cites Work

• Unnamed Item
• Unnamed Item
• The planar \(k\)-means problem is NP-hard
• A local search approximation algorithm for \(k\)-means clustering
• A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems
• On approximate geometric \(k\)-clustering
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A new approximation algorithm for the \(k\)-facility location problem
• A local search approximation algorithm for the \(k\)-means problem with penalties
• The Design of Approximation Algorithms
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy Strikes Back: Improved Facility Location Algorithms
• A Bi-Criteria Approximation Algorithm for k-Means
• Local Search Heuristics for k-Median and Facility Location Problems

This page was built for publication: Local search approximation algorithms for the sum of squares facility location problems