In this paper, we introduce an adaptation of the facility location problem and analyze it within the framework of local differential privacy (LDP). Under this model, we ensure the privacy of client presence at specific locations. When n is the number of points, Gupta et al. [5] established a lower bound of \(\varOmega (\sqrt{n})\) on the approximation ratio for any differentially private algorithm applied to the original facility location problem. As a result, subsequent works have adopted the superset assumption, which may, however, compromise user privacy. We show that this lower bound does not apply to our adaptation by presenting an LDP algorithm that achieves a constant approximation ratio with a relatively small additive factor. Additionally, we provide experimental results demonstrating that our algorithm outperforms the straightforward approach on both synthetically generated and real-world datasets.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Facility Location Problem Under Local Differential Privacy Without Super-Set Assumption

  • Kevin Pfisterer,
  • Quentin Hillebrand,
  • Vorapong Suppakitpaisarn

摘要

In this paper, we introduce an adaptation of the facility location problem and analyze it within the framework of local differential privacy (LDP). Under this model, we ensure the privacy of client presence at specific locations. When n is the number of points, Gupta et al. [5] established a lower bound of \(\varOmega (\sqrt{n})\) on the approximation ratio for any differentially private algorithm applied to the original facility location problem. As a result, subsequent works have adopted the superset assumption, which may, however, compromise user privacy. We show that this lower bound does not apply to our adaptation by presenting an LDP algorithm that achieves a constant approximation ratio with a relatively small additive factor. Additionally, we provide experimental results demonstrating that our algorithm outperforms the straightforward approach on both synthetically generated and real-world datasets.