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

Given a set of clients and a set of facilities with different priority levels in a metric space, the Budgeted Priority \(p\) $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 )\) $(1+\epsilon )$ -approximation algorithm running in \(O(nd\log n)+(p\varepsilon ^{-1})^{p\varepsilon ^{-O(1)}}n^{O(1)}\) $O(ndlogn)+{(p{\epsilon }^{-1})}^{p{\epsilon }^{-O(1)}}{n}^{O(1)}$ time in d-dimensional Euclidean space, where \(n\) $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 )\) $(3+\epsilon )$ .