Given a set of clients and a set of facilities with different priority levels in a metric space, the Budgeted Priority p-Median problem aims to open a subset of facilities and connect each client to an opened facility with the same or a higher priority level, such that the number of opened facilities associated with each priority level is no more than a given upper limit, and the sum of the client-connection costs is minimized.In this paper, we present a data reduction-based approach for limiting the solution search space of the Budgeted Priority $p$-Median problem, which yields a $(1+ \varepsilon$ )-approximation algorithm running in $O(n d \log n)+\left(p \varepsilon^{-1}\right)^{p \varepsilon^{-O(1)}} n^{O(1)}$ time in $d$ dimensional Euclidean space, where $n$ is the size of the input instance and $p$ is the maximal number of opened facilities. The previous best approximation ratio for this problem obtained in the same time is $(3+\varepsilon)$.
Zhen Zhang, Zi-Yun Huang, Zhi-Ping Tian, Li-Mei Liu, Xue-Song Xu, Qi-Long Feng
. On the Budgeted Priority p-Median Problem in High-Dimensional Euclidean Spaces[J]. Journal of the Operations Research Society of China, 2026
, 14(1)
: 309
-324
.
DOI: 10.1007/s40305-023-00533-w
[1] Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithm. 31(1), 228-248(1999)
[2] Cohen-Addad V., Gupta A., Kumar A., Lee E., Li J.: Tight FPT approximations for k-median and k-means. In: The Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, pp. 42(2019)
[3] Cohen-Addad V., Grandoni F., Lee E., Schwiegelshohn C.: Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In: The Proceedings of the 34th ACMSIAM Symposium on Discrete Algorithms, pp. 940-986(2023)
[4] Cohen-Addad V., Esfandiari H., Mirrokni V. S., Narayanan S.: Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets. In: The Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1621-1628(2022)
[5] Kumar A., Sabharwal Y.: The priority k-median problem. In: The Proceedings of the 27th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 71-83(2007)
[6] Goyal, D., Jaiswal, R.: Tight FPT approximation for socially fair clustering. Inf. Process. Lett. 182, 106383(2023)
[7] Goyal, D., Jaiswal, R.: Tight FPT approximation for constrained k-center and k-supplier. Theor. Comput. Sci. 940, 190-208(2023)
[8] Bandyapadhyay S., Lochet W., Saurabh S.: FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii. In: The Proceedings of the 39th International Symposium on Computational Geometry, pp. 12(2023)
[9] Feng Q., Zhang Z., Huang Z., Xu J., Wang J.: A unified framework of FPT approximation algorithms for clustering problems. In: The Proceedings of the 31st International Symposium on Algorithms and Computation, pp. 5(2020)
[10] Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 57(2), pp. 5(2010)
[11] Chen K.: On k-median clustering in high dimensions. In: The Proceedings of the 17th Annual ACMSIAM Symposium on Discrete Algorithms, pp. 1177-1185(2006)
[12] Jaiswal, R., Kumar, A., Sen, S.: A simple D2-sampling based PTAS for k-means and other clustering problems. Algorithmica 70(1), 22-46(2014)
[13] Gupta, A., Krauthgamer, R., Lee, J. R.: Bounded geometries, fractals, and low-distortion embeddings. In: The Proceedings of the 44th IEEE Annual Symposium on Foundations of Computer Science, pp. 534-543(2003)
[14] Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148-1184(2006)
[15] Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math. 26, 189-206(1984)
[16] Narayanan S., Nelson J.: Optimal terminal dimensionality reduction in Euclidean space. In: The Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 1064-1069(2019)
