Solving bin-packing problems under privacy preservation: Possibilities and trade-offs

Rowan Hoogervorst*, Yingqian Zhang, Gamze Tillem, Zekeriya Erkin, Sicco Verwer

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

7 Citations (Scopus)

Abstract

We investigate the trade-off between privacy and solution quality that occurs when a k-anonymized database is used as input to the bin-packing optimization problem. To investigate the impact of the chosen anonymization method on this trade-off, we consider two recoding methods for k-anonymity: full-domain generalization and partition-based single-dimensional recoding. To deal with the uncertainty created by anonymization in the bin-packing problem, we utilize stochastic programming and robust optimization methods. Our computational results show that the trade-off is strongly dependent on both the anonymization and optimization method. On the anonymization side, we see that using single dimensional recoding leads to significantly better solution quality than using full domain generalization. On the optimization side, we see that using stochastic programming, where we use the multiset of values in an equivalence class, considerably improves the solutions. While publishing these multisets makes the database more vulnerable to a table linkage attack, we argue that it is up to the data publisher to reason if such a loss of anonymization weighs up to the increase in optimization performance.

Original languageEnglish
Pages (from-to)203-216
Number of pages14
JournalInformation Sciences
Volume500
DOIs
Publication statusPublished - 2019

Keywords

  • Bin-packing
  • Data anonymization
  • k-anonymity
  • Robust optimization
  • Stochastic programming

Fingerprint

Dive into the research topics of 'Solving bin-packing problems under privacy preservation: Possibilities and trade-offs'. Together they form a unique fingerprint.

Cite this