A Local Search Approximation Algorithm for the k-means Problem with Penalties

被引：5

作者：

Zhang, Dongmei ^{[1
]}

Hao, Chunlin ^{[2
]}

Wu, Chenchen ^{[3
]}

Xu, Dachuan ^{[2
]}

Zhang, Zhenning ^{[2
]}

机构：

[1] Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

[2] Beijing Univ Technol, Coll Appl Sci, Dept Informat & Operat Res, Beijing 100124, Peoples R China

[3] Tianjin Univ Technol, Coll Sci, Tianjin 300384, Peoples R China

来源：

COMPUTING AND COMBINATORICS, COCOON 2017 | 2017年 / 10392卷

关键词：

Approximation algorithm; k-means; Penalty; Local search;

D O I：

10.1007/978-3-319-62389-4_47

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper, we study the k-means problem with (nonuniform) penalties (k-MPWP) which is a natural generalization of the classic k-means problem. In the k-MPWP, we are given an n-client set D subset of R-d, a penalty cost p(j) > 0 for each j is an element of D, and an integer k <= n. The goal is to open a center subset F subset of R-d with vertical bar F vertical bar <= k and to choose a client subset P subset of D as the penalized client set such that the total cost (including the sum of squares of distance for each client in D \ P to the nearest open center and the sum of penalty cost for each client in P) is minimized. We offer a local search (81 + epsilon)-approximation algorithm for the k-MPWP by using single-swap operation. We further improve the above approximation ratio to (25 + epsilon) by using multi-swap operation.

引用

页码：568 / 574

页数：7

共 19 条

[1] NP-hardness of Euclidean sum-of-squares clustering [J].

Aloise, Daniel ;

Deshpande, Amit ;

Hansen, Pierre ;

Popat, Preyas .

MACHINE LEARNING, 2009, 75 (02) :245-248

[2] Local search heuristics for k-median and facility location problems [J].

Arya, V ;

Garg, N ;

Khandekar, R ;

Meyerson, A ;

Munagala, K ;

Pandit, V .

SIAM JOURNAL ON COMPUTING, 2004, 33 (03) :544-562

[3]

Bandyapadhyay S., 2016, P SOCG

[4]

Charikar M., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P1, DOI 10.1145/301250.301257

[5]

Charikar M., 1999, 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), P378, DOI 10.1109/SFFCS.1999.814609

[6]

Charikar M, 2001, SIAM PROC S, P642

[7]

Dasgupta, 2007, CS20080916 U CAL DEP

[8]

Georgogiannis A., 2016, PROC ADV NEURAL INFO, P2891

[9] A local search approximation algorithm for k-means clustering [J].

Kanungo, T ;

Mount, DM ;

Netanyahu, NS ;

Piatko, CD ;

Silverman, R ;

Wu, AY .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 28 (2-3) :89-112

[10]

Li S, 2013, STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, P901

← 1 2 →