Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties

DOI10.1007/s40305-022-00394-9MaRDI QIDQ6566778

Dong-lei Du, Dongmei Zhang, Fan Yuan, Da-Chuan Xu

Publication date: 3 July 2024

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmlocal search\(k\)-meanspenalty

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A local search approximation algorithm for \(k\)-means clustering
• Local search algorithms for the red-blue median problem
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• NP-hardness of Euclidean sum-of-squares clustering
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• On approximate geometric \(k\)-clustering
• An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution
• An improved approximation algorithm for the \(k\)-means problem with penalties
• Local search approximation algorithms for the \(k\)-means problem with penalties
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The Planar k-Means Problem is NP-Hard
• Local Search Heuristics for k-Median and Facility Location Problems
• Least squares quantization in PCM
• An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization

This page was built for publication: Local search yields a PTAS for fixed-dimensional \(k\)-means problem with penalties