Facility Location Problem under Local Differential Privacy without Super-set Assumption
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915350018260992 |
|---|---|
| author | Pfisterer, Kevin Hillebrand, Quentin Suppakitpaisarn, Vorapong |
| author_facet | Pfisterer, Kevin Hillebrand, Quentin Suppakitpaisarn, Vorapong |
| contents | 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. established a lower bound of $Ω(\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 super-set 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_15224 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Facility Location Problem under Local Differential Privacy without Super-set Assumption Pfisterer, Kevin Hillebrand, Quentin Suppakitpaisarn, Vorapong Cryptography and Security 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. established a lower bound of $Ω(\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 super-set 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. |
| title | Facility Location Problem under Local Differential Privacy without Super-set Assumption |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2506.15224 |