LOCAL SEARCH YIELDS APPROXIMATION SCHEMES FOR k-MEANS AND k-MEDIAN IN EUCLIDEAN AND MINOR-FREE METRICS

被引：42

作者：

Cohen-Addad, Vincent ^{[1
]}

Klein, Philip N. ^{[2
]}

Mathieu, Claire ^{[3
]}

机构：

[1] Sorbonne Univ, LIP6, F-75252 Paris 05, France

[2] Brown Univ, Dept Comp Sci, Providence, RI 02912 USA

[3] Ecole Normale Super, Dept Informat, F-75001 Paris, France

来源：

SIAM JOURNAL ON COMPUTING | 2019年 / 48卷 / 02期

关键词：

approximation schemes; k-means; k-median; facility location; Euclidean metric; planar graph; minor-free graphs; FACILITY LOCATION; ALGORITHMS; HEURISTICS;

D O I：

10.1137/17M112717X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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; and (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/epsilon(Theta(1)) centers.

引用

页码：644 / 667

页数：24

共 47 条

[1] Aarts E., 1997, Local Search in Combinatorial Optimization, V1st
[2] ALON N, 1990, PROCEEDINGS OF THE TWENTY SECOND ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, P293, DOI 10.1145/100216.100254
[3] [Anonymous], 2015, 31 INT S COMP GEOM S, DOI DOI 10.4230/LIPICS.S0CG.2015.329
[4] [Anonymous], 2015, 31 INT S COMP GEOM S, DOI 10.4230/LIPICS.SOCG.2015.754
[5] [Anonymous], P 12 INT BAIK WORKSH
[6] Arora S., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P106, DOI 10.1145/276698.276718
[7] Smoothed Analysis of the k-Means Method
Arthur, David
Manthey, Bodo
Roeglin, Heiko
[J]. JOURNAL OF THE ACM, 2011, 58 (05)
[8] WORST-CASE AND SMOOTHED ANALYSIS OF THE ICP ALGORITHM, WITH AN APPLICATION TO THE k-MEANS METHOD
Arthur, David
Vassilvitskii, Sergei
[J]. SIAM JOURNAL ON COMPUTING, 2009, 39 (02) : 766 - 782
[9] Local search heuristics for k-median and facility location problems
Arya, V
Garg, N
Khandekar, R
Meyerson, A
Munagala, K
Pandit, V
[J]. SIAM JOURNAL ON COMPUTING, 2004, 33 (03) : 544 - 562
[10] Awasthi Pranjal, 2012, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Proceedings 15th International Workshop, APPROX 2012 and 16th International Workshop, RANDOM 2012, P37, DOI 10.1007/978-3-642-32512-0_4

← 1 2 3 4 5 →