.png){kind=icon}
.png){kind=icon}
Return
Location Problems with Privacy
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-10759-6_2.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We examine well known facility location problems under the privacy challenges posed by big data environments. For a given set of n points U is an element of R-d, previous works have introduced the Topology Descriptor Grid (TDG) [13, 14], a privacy-preserving framework under which some approximate solutions are possible for a variety of clustering problems. In this paper, we introduce the Equidistant Location Estimation using Concentric Circles (LECC) framework in R-2, which obfuscates exact point locations while preserving their relative distances to a predetermined point. We show, under this new framework, how to obtain 2 + O(1/n)-approximate solutions for the 1-center, 1-median, 1-mean, and k-centrum problems, and O(k), O(k), O(k(2)) approximations for the k-center, k-median and k-means problems, respectively. For the TDG framework we provide a (root d, k(d-1)),(d, k(d-1)), and(d(2), k(d-1)) approximations for the k-center, k-median, and k-means problems, respectively.
Keywords:
Facility location
Privacy
Approximation algorithms
Journal
C
IF:
0
Papers:
25
Citations:
0