On the Budgeted Priority p-Median Problem in High-Dimensional Euclidean Spaces

doi:10.1007/s40305-023-00533-w

Journal of the Operations Research Society of China ›› 2026, Vol. 14 ›› Issue (1): 309-324.doi: 10.1007/s40305-023-00533-w

Previous Articles Next Articles

On the Budgeted Priority p-Median Problem in High-Dimensional Euclidean Spaces

Zhen Zhang^1,2, Zi-Yun Huang³, Zhi-Ping Tian^1,2, Li-Mei Liu^1,2, Xue-Song Xu^1,2, Qi-Long Feng^2,4

1 School of Advanced Interdisciplinary Studies, Hunan University of Technology and Business, Changsha 410205, Hunan, China;
2 Xiangjiang Laboratory, Changsha 410205, Hunan, China;
3 Department of Computer Science and Software Engineering, Penn State Erie, The Behrend College, Erie, PA 16563, USA;
4 School of Computer Science and Engineering, Central South University, Changsha 410012, Hunan, China

Received:2023-09-04 Revised:2023-11-20 Online:2026-03-30 Published:2026-03-16
Contact: Li-Mei Liu E-mail:seagullm@163.com
Supported by:
This work was supported by the National Natural Science Foundation of China (Nos.62202161,62172446,and 62376092),Natural Science Foundation of Hunan Province (No.2023JJ40240),and Open Project of Xiangjiang Laboratory (Nos.22XJ02002 and 22XJ03005).

Abstract

Abstract: 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)$.

Key words: Approximation algorithms, Facility location, p-Median

CLC Number:

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.

TrendMD

References

[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)

On the Budgeted Priority p-Median Problem in High-Dimensional Euclidean Spaces

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 12

Recommended Articles

Metrics

Comments

[1]	Peng-Xiang Pan, Jun-Ran Lichen, Wen-Cheng Wang, Li-Jian Cai, Jian-Ping Li. Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints [J]. Journal of the Operations Research Society of China, 2025, 13(2): 535-554.
[2]	Pei-Jia Yang, Wen-Chang Luo. Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties [J]. Journal of the Operations Research Society of China, 2025, 13(1): 287-296.
[3]	Jian-Ping Li, Wen-Cheng Wang, Jun-Ran Lichen, Yu-Jie Zheng. Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R² Using Stock Pieces of Materials with Fixed Length [J]. Journal of the Operations Research Society of China, 2024, 12(4): 996-1021.
[4]	Jian-Ping Li, Su-Ding Liu, Jun-Ran Lichen, Peng-Xiang Pan, Wen-Cheng Wang. Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem [J]. Journal of the Operations Research Society of China, 2024, 12(3): 729-755.
[5]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Correlation Clustering [J]. Journal of the Operations Research Society of China, 2023, 11(4): 911-924.
[6]	Zhong-Zheng Tang, Chen-Hao Wang, Meng-Qi Zhang, Ying-Chao Zhao. Strategyproof Facility Location with Limited Locations [J]. Journal of the Operations Research Society of China, 2023, 11(3): 553-567.
[7]	Feng-Min Wang, Jia-Jia Wang, Na Li, Yan-Jun Jiang, Shi-Cheng Li. A Cost-Sharing Scheme for the k-Level Facility Location Game with Penalties [J]. Journal of the Operations Research Society of China, 2022, 10(1): 173-182.
[8]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal [J]. Journal of the Operations Research Society of China, 2021, 9(4): 883-892.
[9]	Esmaeil Afrashteh, Behrooz Alizadeh, Fahimeh Baroughi. Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks [J]. Journal of the Operations Research Society of China, 2021, 9(1): 99-117.
[10]	Jian Li· Yu Liu. Approximation Algorithms for Stochastic Combinatorial Optimization Problems [J]. Journal of the Operations Research Society of China, 2016, 4(1): 1-.
[11]	Chen-Chen Wu · Da-Chuan Xu · Jia Shu. An Approximation Algorithm for the Stochastic Fault-Tolerant Facility Location Problem [J]. Journal of the Operations Research Society of China, 2013, 1(4): 511-522.
[12]	Jia-Ting Shao · Da-Chuan Xu. An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties [J]. Journal of the Operations Research Society of China, 2013, 1(3): 339-346.