Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics

2016/03/31 by Cohen-Addad, Vincent, Klein, Philip N., Mathieu, Claire · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1603.09535

Abstract

We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) k-median and k-means in edge-weighted planar graphs; (3) k-means in Euclidean spaces of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results extend to cost functions that are the p-th power of the shortest-path distance. The algorithm is local search where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding 1/ε^O(1) centers.

Cited by

• The Computational Complexity of Almost Stable Clustering with Penalties

Related

• Efficient approximation schemes for uniform-cost clustering problems in planar graphs
• A Polynomial-Time Approximation Scheme for Facility Location on Planar\n Graphs
• Local Search Yields a PTAS for k-Means in Doubling Metrics
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Simpler Analyses of Local Search Algorithms for Facility Location