The Seeding and Bi-Criteria Algorithms for Fuzzy k-Median Problem

The [Formula: see text]-median problem and fuzzy [Formula: see text]-median problem belong to hard clustering and soft clustering, respectively. Hard clustering involves assigning each client to only one facility, while soft clustering means that there is no clear boundary between clusters; that is, each client can be served by multiple facilities. In our paper, we mainly discuss the seeding and bi-criteria algorithms for fuzzy [Formula: see text]-median problem. Firstly, we propose the seeding algorithms, and present the complete analysis of the approximation factor of [Formula: see text] based on the initialization of the fuzzy [Formula: see text]-median++ algorithm for fuzzy [Formula: see text]-median problem. Secondly, we design a bi-criteria algorithm reducing the approximation ratio to [Formula: see text]. Thirdly, we generalize these two kinds of algorithms to a general function. Finally, numerical experiments are carried out to demonstrate the effectiveness of these algorithms.