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

Author:

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

Indexed by:

CPCI-S

Abstract:

Clustering is one of the most fundamental tools in artificial intelligence, machine learning, and data mining. In this paper, we follow one of the recent mainstream topics of clustering, Sum of Radii (SoR), which naturally arises as a balance between the folklore k-center and k-median. SoR aims to determine a set of k balls, each centered at a point in a given dataset, such that their union covers the entire dataset while minimizing the sum of radii of the k balls. We propose a general technical framework to overcome the challenge posed by varying radii in SoR, which yields fixed-parameter tractable (fpt) algorithms with respect to k (i.e., whose running time is f(k)ploy(n) for some f). Our framework is versatile and obtains fpt approximation algorithms with constant approximation ratios for SoR as well as its variants in general metrics, such as Fair SoR and Matroid SoR, which significantly improve the previous results.

Keyword:

Author Community:

  • [ 1 ] [Chen, Xianrun]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen, Peoples R China
  • [ 2 ] [Xu, Yicheng]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen, Peoples R China
  • [ 3 ] [Zhang, Yong]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen, Peoples R China
  • [ 4 ] [Chen, Xianrun]Univ Chinese Acad Sci, Beijing, Peoples R China
  • [ 5 ] [Xu, Yicheng]Univ Chinese Acad Sci, Beijing, Peoples R China
  • [ 6 ] [Zhang, Yong]Univ Chinese Acad Sci, Beijing, Peoples R China
  • [ 7 ] [Xu, Dachuan]Beijing Univ Technol, Beijing, Peoples R China

Reprint Author's Address:

  • [Xu, Yicheng]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen, Peoples R China;;[Xu, Yicheng]Univ Chinese Acad Sci, Beijing, Peoples R China;;

Show more details

Related Keywords:

Related Article:

Source :

THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 18

ISSN: 2159-5399

Year: 2024

Page: 20666-20673

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 9

Affiliated Colleges:

Online/Total:1339/10904043
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.