Fixed-parameter tractability of capacitated k-facility location

Xiangyan KONG, Zhen ZHANG

PDF(752 KB)
PDF(752 KB)
Front. Comput. Sci. ›› 2023, Vol. 17 ›› Issue (6) : 176408. DOI: 10.1007/s11704-023-2231-9
LETTER

Fixed-parameter tractability of capacitated k-facility location

Author information +
History +

Graphical abstract

Cite this article

Download citation ▾
Xiangyan KONG, Zhen ZHANG. Fixed-parameter tractability of capacitated k-facility location. Front. Comput. Sci., 2023, 17(6): 176408 https://doi.org/10.1007/s11704-023-2231-9

References

[1]
Xu X H, Du Z J, Chen X H, Cai C G . Confidence consensus-based model for large-scale group decision making: a novel approach to managing non-cooperative behaviors. Information Sciences, 2019, 477: 410–427
[2]
Xu X, Dou W, Zhang X, Hu C, Chen J . A traffic hotline discovery method over cloud of things using big taxi GPS data. Software: Practice and Experience, 2017, 47( 3): 361–377
[3]
Rong H, Zhang H, Xiao S, Li C, Hu C . Optimizing energy consumption for data centers. Renewable and Sustainable Energy Reviews, 2016, 58: 674–691
[4]
Cohen-Addad V, Gupta A, Kumar A, Lee E, Li J. Tight FPT approximations for k-median and k-means. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming. 2019, 42: 1−42: 14
[5]
Aardal K, van den Berg P L, Gijswijt D, Li S . Approximation algorithms for hard capacitated k-facility location problems. European Journal of Operational Research, 2015, 242( 2): 358–368
[6]
Han L, Xu D, Du D, Zhang D . A local search approximation algorithm for the uniform capacitated k-facility location problem. Journal of Combinatorial Optimization, 2018, 35( 2): 409–423
[7]
Jiang Y, Xu D, Du D, Wu C, Zhang D . An approximation algorithm for soft capacitated k-facility location problem. Journal of Combinatorial Optimization, 2018, 35( 2): 493–511
[8]
Byrka J, Fleszar K, Rybicki B, Spoerhase J. Bi-factor approximation algorithms for hard capacitated k-median problems. In: Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms. 2015, 722−736
[9]
Adamczyk M, Byrka J, Marcinkowski J, Meesum S M, Wlodarczyk M. Constant-factor FPT approximation for capacitated k-Median. In: Proceedings of the 27th Annual European Symposium on Algorithms. 2019, 1: 1−1: 14

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 62202161, 62172446), Open Project of Xiangjiang Laboratory (22XJ02002), Central South University Research Programme of Advanced Interdisciplinary Studies (2023QYJC023), Scientific Research Fund of Hunan Provincial Education Department (20C0538, 21A0376), and Project of Hunan Social Science Achievement Appraisal Committee (XSP21YBZ113). The authors are thankful to the reviewers for the valuable comments and suggestions, which are very helpful for improving this work.

Supporting Information

The supporting information is available online at journal.hep.cn and link.springer.com.

RIGHTS & PERMISSIONS

2023 Higher Education Press
AI Summary AI Mindmap
PDF(752 KB)

Accesses

Citations

Detail

Sections
Recommended

/