• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Chen, Xianrun (Chen, Xianrun.) | Han, Lu (Han, Lu.) | Xu, Dachuan (Xu, Dachuan.) | Xu, Yicheng (Xu, Yicheng.) | Zhang, Yong (Zhang, Yong.)

Indexed by:

EI Scopus

Abstract:

We revisit the classical metric k-median/means with outliers in this paper, whose proposal dates back to (Charikar, Khuller, Mount, and Narasimhan SODA’01). Though good approximation algorithms have been proposed, referring to the state-of-the-art (6.994+ Ε )-approximation (Gupta, Moseley and Zhou ICALP’21) for k-median with outliers and (53.002+ Ε )-approximation (Krishnaswamy, Li, and Sandeep SODA’18) for k-means with outliers respectively, we are interested in finding efficient fpt (fixed-parameter tractable) approximations, following a recent research mainstream for constrained clusterings. As our main contribution, we propose a simple but efficient technical framework that yields a (3 + Ε) / (9 + Ε) -approximation for k-median/means with outliers, albeit in ((m+ k) / Ε) O(k)· nO(1) time. It is notable that our results match with previous result (Goyal, Jaiswal, and Kumar IPEC’20) in terms of ratio and asymptotic running time. But as aforementioned, our technique is much more simplified and straightforward, where instead of considering the whole client set, we restrict ourselves to finding a good approximate facility set for coreset, which can be done easily in fpt time even with provably small loss. Similar idea can be applied to more constrained clustering problems whose coresets have been well-studied. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Keyword:

K-means clustering Statistics Approximation algorithms

Author Community:

  • [ 1 ] [Chen, Xianrun]Chinese Academy of Sciences, Shenzhen Institute of Advanced Technology, Shenzhen, China
  • [ 2 ] [Han, Lu]Beijing University of Posts and Telecommunications, Beijing, China
  • [ 3 ] [Xu, Dachuan]Beijing University of Technology, Beijing, China
  • [ 4 ] [Xu, Yicheng]Chinese Academy of Sciences, Shenzhen Institute of Advanced Technology, Shenzhen, China
  • [ 5 ] [Zhang, Yong]Chinese Academy of Sciences, Shenzhen Institute of Advanced Technology, Shenzhen, China

Reprint Author's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2024

Volume: 14423 LNCS

Page: 295-302

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 3

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:480/6005363
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.