Name
Title | ||
|---|---|---|
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics |
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 space 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 pth 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/ε
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup>
centers. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/FOCS.2016.46 | 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | Field | DocType |
approximation schemes,k-means,k-median,facility location,Euclidean metric,planar graph,minor-free graphs | Discrete mathematics,Combinatorics,Chordal graph,Euclidean distance,Euclidean geometry,Local search (optimization),1-planar graph,Planar graph,Metric dimension,Mathematics,Bounded function | Conference |
ISSN | ISBN | Citations |
0272-5428 | 978-1-5090-3934-0 | 4 |
PageRank | References | Authors |
0.39 | 29 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Cohen-Addad | 1 | 85 | 25.47 |
| Philip N. Klein | 2 | 2681 | 256.19 |
| Claire Mathieu | 3 | 452 | 25.78 |