Near-Optimal Differentially Private $k$-Center for Service Computing with Access Control

Many applications in service computing systems, such as location-based services (LBS), use the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-center problem to guide service placement and improve the quality of service. In such settings, access control (AC) is commonly employed to protect client privacy. However, as we demonstrate in this paper, privacy leakage can still occur even in the presence of AC. To address this issue, we study the AC-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-center problem under differential privacy (DP), which has emerged as a leading paradigm for mitigating privacy risks by injecting calibrated noise while providing guarantees that remain robust against adversaries with arbitrary prior knowledge or attack strategies. We first propose a framework that integrates access control into the service placement process, thereby establishing a balance between privacy preservation and solution utility. Building on this framework, we present a novel algorithm for the differentially private AC-<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-center problem that achieves the best possible 2-approximation ratio with an additive error. By leveraging intermediate structures from the continuous <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-center problem and Voronoi diagrams, our approach reduces the additive error in the approximation ratio compared with state-of-the-art methods. Finally, we conduct extensive experiments on three real-world geographical datasets, demonstrating that our algorithm outperforms existing baselines in both solution quality and runtime efficiency.