Clustering a set of clients according to their distances to a selected set of opened facilities is a frequently encountered task in theoretical computer science,where the following trade-off needs to be considered:We want to connect each client to a nearby opened facility,while only a limited number of facilities can be opened.In this paper we consider an extensively studied problem that formalizes this task,called lower-bounded k-median.An instance(C,F,k,τ)of the problem consists of a set C of clients,a set F of facilities,and a positive integer k,where the clients and facilities from C U F are in a metric space,and each f ∈ F is associated with a lower bound τ(f)∈(0,|C|].A feasible solution(H,σ)to the instance is specified by a subset H ⊆ F satisfying|H|≤k and a mapping σ:C→H satisfying|σ-1(f)|≥τ(f)for each f ∈ H.The cost of(H,σ)is ∑c∈Cδ(c,σ(c)),where δ(c,σ(c))is the distance from c to σ(c).The problem aims to find a feasible solution with minimal cost.Designing algorithms for the lower-bounded k-median problem remains a vibrant area of research owing to its significance in many fields related to facility location and clustering,including transportation planning,network optimization,and privacy-preserving computing.In this paper we study the lower-bounded k-median problem for the case where the clients and facilities are in d-dimensional Euclidean space,under the assumption that k is small.This assumption is reasonable as the maximum number of opened facilities is much smaller than the input size in most practical scenarios regarding the problem.Given an instance of the problem with a total of n clients and facilities,it is easy to show that an optimal solution can be found by brute-force enumeration inn O(k)time,but we ask:What can be done in fixed-parameter tractable time parameterized by k(i.e.,nO(1)h(k)time for a positive function h)?Our algorithm starts with selecting a set of clients using D-sampling.Given a small positive constant ε,we prove that a set of O(kε-3)clients selected with D-sampling ensures the inclusion of clients proximate to the facilities opened in an optimal solution.By partitioning a set of closed balls centered at these O(kε-3)clients,we construct a small candidate set of opened facilities.We demonstrate that enumerating this candidate set yields a(1+ε)-approximation algorithm with running time exponential in k and the dimensionality of the space.Combining this algorithm with a dimensionality-reduction method that maps the clients and facilities to εO(1)(logk+loglogn)-dimensional Euclidean space,we give a(1+e)-approximation algorithm with running time O(ndk+(kε-1)kε-O(1)nO(1))for the lower-bounded k-median problem.The previous best fixed-parameter tractable approximation guarantee for the problem is a ratio of 3+ε,and(1+ε)-approximation algorithms with similar running time exist only in the case where the facilities can be opened at any location of the space and are uniform in the associated lower bounds.Our primary technical contribution,crucial for achieving the fixed-parameter tractable time(1+ε)-approximation algorithm,lies in a novel approach to reducing the solution search space.We believe this approach holds potential applicability in other clustering problems and is of independent interest.
NETL
NSTL
万方数据
