The Approximation Algorithms for Constrained Fuzzy Center Problems

By generalizing the classical [Formula: see text]-center and matroid center problems, we formulate fuzzy models that belong to the category of soft clustering. We first develop a greedy algorithm for the fuzzy [Formula: see text]-center problem that achieves the approximation ratio with [Formula: see text], where the parameter [Formula: see text] controls the fuzziness. We then further extend this model by imposing a matroid constraint instead of a cardinality constraint, thereby formulating the fuzzy matroid center problem. For this more general problem, we propose an efficient algorithm, achieving the approximation ratio with [Formula: see text], where [Formula: see text] is the matroid rank and [Formula: see text] is an arbitrary positive number. Furthermore, for the matroid center problem, we significantly improve the time complexity of the existing 3-approximation algorithm by exponentially reducing the number of candidate subgraphs. Finally, we conduct numerical experiments to evaluate the performance of our algorithm for the fuzzy [Formula: see text]-center problem with the fuzziness parameter set to 2.