The Approximation Algorithms for Constrained Fuzzy Center Problems
International Journal of Foundations of Computer Science · 30.10.2026 · 1-16
DOI: 10.1142/s0129054126490080 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 30.10.2026. Verfasst von Jiawei Chen und 3 weiteren Autor:innen. Gefördert von: Natural Science Foundation of Shandong Province, National Natural Science Foundation of China.
Abstract (Originalsprache)
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.
Förderung
- Natural Science Foundation of Shandong Province
- National Natural Science Foundation of China
Zitieren
APA
Chen, J., Liu, Q., Zhou, Y., & Li, M. (2026). The Approximation Algorithms for Constrained Fuzzy Center Problems. International Journal of Foundations of Computer Science, 1-16. https://doi.org/10.1142/s0129054126490080
Vancouver
Chen J, Liu Q, Zhou Y, Li M. The Approximation Algorithms for Constrained Fuzzy Center Problems. International Journal of Foundations of Computer Science. 2026:1-16. doi:10.1142/s0129054126490080
BibTeX
@article{Chen2026,
author = {Chen, Jiawei and Liu, Qian and Zhou, Yang and Li, Min},
title = {The Approximation Algorithms for Constrained Fuzzy Center Problems},
journal = {International Journal of Foundations of Computer Science},
year = {2026},
pages = {1--16},
doi = {10.1142/s0129054126490080}
}
EUVIMED