The controlled rounding problem: Relaxations and complexity issues

Summary Controlled rounding is a procedure that perturbs tabular data collected from respondents in such a way as to preserve the anonymity of the respondents while maintaining the integrity of the data. Controlled rounding techniques are regularly used by the United States Bureau of the Census and its counterparts in other countries. This paper discusses the complexity of the three-dimensional controlled rounding problem. In particular, the three-dimensional, zero-restricted controlled rounding problem is shown to be NP-complete. As zero-restricted controlled roundings may fail to exist, various relaxations of this basic rounding problem have been defined. The paper introduces a sequence of such relaxations and proceeds to address the existence of solutions and complexity issues for the relaxed problems.

---

Zusammenfassung Die Technik des kontrollierten Rundens (Controlled Rounding) wird von Behörden wie dem United States Bureau of Census benutzt, um in mehrdimensionalen Tabellen oder Matrizen erfaßte statistische Daten durch Approximation so zu verändern, daß sowohl die Anonymität von Einzeldaten (Matrixeinträgen) als auch die Integrität der Gesamtdaten (Zeilensummen, Spaltensummen etc.) gewährleistet ist. In dieser Arbeit behandeln wir die Komplexität und Lösbarkeit des dreidimensionalen Rundungsproblems und diskutieren eine Hierarchie von Relaxationen, die bei Nichtlösbarkeit des Ausgangsproblems alternative, nahezu zulässige Lösungen liefern.