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

author:

Lin, Z. (Lin, Z..) [1] | Guo, L. (Guo, L..) [2] | Jia, C. (Jia, C..) [3]

Indexed by:

Scopus

Abstract:

Emerging applications are imposing challenges for incorporating fairness constraints into k-center clustering in the streaming setting. Different from the traditional k-center problem, the fairness constraints require that the input points be divided into disjoint groups and the number of centers from each group is constrained by a given upper bound. Moreover, observing the applications of fair k-center in massive datasets, we consider the problem in the streaming setting, where the data points arrive in a streaming manner that each point can be processed at its arrival. As the main contributions, we propose a two-pass streaming algorithm for the fair k-center problem with two groups, achieving an approximation ratio of 3+ϵ and consuming only O(klogn) memory and O(k) update time, matching the state-of-art ratio for the offline setting. Then, we show that the algorithm can be easily improved to a one-pass streaming algorithm with an approximation ratio of 7+ϵ and the same memory complexity and update time. Moreover, we show that our algorithm can be simply tuned to solve the case with an arbitrary number of groups while achieving the same ratio and space complexity. Lastly, we carried out extensive experiments to evaluate the practical performance of our algorithm compared with the state-of-the-art algorithms. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.

Keyword:

Approximation algorithm Fair k-center clustering Streaming algorithm

Community:

  • [ 1 ] [Lin Z.]School of Mathematics and Statistics, Fuzhou University, Fuzhou, 350116, China
  • [ 2 ] [Guo L.]School of Mathematics and Statistics, Fuzhou University, Fuzhou, 350116, China
  • [ 3 ] [Guo L.]School of Computer Science, Qilu University of Technology (Shandong Academy of Sciences), Jinan, 250316, China
  • [ 4 ] [Jia C.]School of Accounting, Information Systems and Supply Chain, RMIT University, Melbourne, 3000, VIC, Australia
  • [ 5 ] [Jia C.]School of Computer Science, Qilu University of Technology (Shandong Academy of Sciences), Jinan, 250316, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2024

Volume: 14647 LNAI

Page: 105-117

Language: English

0 . 4 0 2

JCR@2005

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 2

Affiliated Colleges:

Online/Total:91/10272953
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1