EUVIMEDEUVIMED entdecken
Crossref

The Approximation Algorithms for Constrained Fuzzy Center Problems

Jiawei Chen, Qian Liu, Yang Zhou, Min Li

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →