## Ñ§ÊõÐÅÏ¢

µ±Ç°Î»ÖÃ: > Ñ§ÊõÐÅÏ¢ >

# ¹ØÓÚ¾Ù°ì¡¶A local search approximation algorithm for the k-means problem with penalties¡·Ñ§Êõ±¨¸æµÄÍ¨Öª

·¢²¼ÈÕÆÚ£º2017-06-07 10:00      À´Ô´£ºÎ´Öª      µã»÷: ´Î
Õª   Òª: In this talk, 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 $\mathcal{D}\subset\mathbb{R}^d$, a penalty cost $p_j>0$ for each $j \in\mathcal{D}$, and an integer k<=n. The goal is to open a center subset $F\subset\mathbb{R}^d$ with $|F| \le k$ and to choose a client subset $P \subseteq\mathcal{D}$ as the penalized client set such that the total cost (including the sum of squares of distance for each client in $\mathcal{D} \setminus 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+ \varepsilon)$-approximation algorithm for the k-MPWP by using single-swap operation. We further improve the above approximation ratio to $(25+\varepsilon )$ by using multi-swap operation. (Joint work with Dongmei Zhang, Chunlin Hao, Chenchen Wu, and Zhenning Zhang)
                                                          Éòº½¿ÆÐ­
2017/6/7