2026-07-21T23:19:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15465 2024-03-06T10:55:21Z ddc:004 open_access

Anonymity-Preserving Space Partitions Hébert-Johnson, Úrsula Sonar, Chinmay Suri, Subhash Surianarayanan, Vaishali Anonymity Hitting Set LP Constant Approximation Fixed-Parameter Tractable Space Partitions Parameterized Complexity We consider a multidimensional space partitioning problem, which we call Anonymity-Preserving Partition. Given a set P of n points in ℝ^d and a collection H of m axis-parallel hyperplanes, the hyperplanes of H partition the space into an arrangement A(H) of rectangular cells. Given an integer parameter t > 0, we call a cell C in this arrangement deficient if 0 < |C ∩ P| < t; that is, the cell contains at least one but fewer than t data points of P. Our problem is to remove the minimum number of hyperplanes from H so that there are no deficient cells. We show that the problem is NP-complete for all dimensions d ≥ 2. We present a polynomial-time d-approximation algorithm, for any fixed d, and we also show that the problem can be solved exactly in time (2d-0.924)^k m^O(1) + O(n), where k is the solution size. The one-dimensional case of the problem, where all hyperplanes are parallel, can be solved optimally in polynomial time, but we show that a related Interval Anonymity problem is NP-complete even in one dimension. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Úrsula Hébert-Johnson and Chinmay Sonar and Subhash Suri and Vaishali Surianarayanan 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.32 urn:nbn:de:0030-drops-154654 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.32 eng https://creativecommons.org/licenses/by/4.0/legalcode