Name
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/epsilon^{O(1)}$ centers. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Data Structures and Algorithms | Discrete mathematics,Graph,Combinatorics,Facility location problem,Local search (optimization),Euclidean geometry,Cluster analysis,Mathematics,Planar graph,Bounded function |
DocType | Volume | Citations |
Journal | abs/1603.09535 | 3 |
PageRank | References | Authors |
0.38 | 16 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Cohen-Addad | 1 | 85 | 25.47 |
| Philip N. Klein | 2 | 2681 | 256.19 |
| Claire Mathieu | 3 | 6 | 2.78 |